【競技プログラミング】AtCoder Beginner Contest 254_D問題

問題

アプローチ

素因数分解と平方数の性質を利用して、条件を満たす組み合わせを数え上げる。

解法手順

1. 入力として整数Nを受け取る。

2. カウンター変数cntを0で初期化する。

3. 1からNまでの各整数iに対して以下の処理を行う：
   a. iを素因数分解し、平方数部分を取り除く。
   b. 残った数をjとする。
   c. j×k^2がN以下となる最大のkを求める。
   d. kの値だけcntに加算する。

4. すべての処理が終わったら、cntを出力する。

ACコード

ac.py

import math

def solve(N):
    # 1. 入力として整数Nを受け取る（この関数の引数として渡されています）

    # 2. カウンター変数cntを0で初期化する
    cnt = 0

    # 素因数分解を効率的に行うための前処理
    # エラトステネスの篩を用いて素数リストを作成
    primes = []
    is_prime = [True] * (N + 1)
    for i in range(2, N + 1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i * i, N + 1, i):
                is_prime[j] = False

    # 3. 1からNまでの各整数iに対して処理を行う
    for i in range(1, N + 1):
        # a. iを素因数分解し、平方数部分を取り除く
        j = i
        for p in primes:
            if p * p > j:
                break
            while j % (p * p) == 0:
                j //= p * p

        # b. 残った数をjとする（上記のループで既に計算済み）

        # c. j×k^2がN以下となる最大のkを求める
        k = int(math.sqrt(N // j))

        # d. kの値だけcntに加算する
        cnt += k

    # 4. すべての処理が終わったら、cntを出力する
    return cnt

if __name__=="__main__":
    N = int(input())  # 標準入力からNを読み込む
    result = solve(N)  # solve関数を呼び出して結果を得る
    print(result)  # 結果を出力する

一覧ページへのリンク

一覧ページ