問題
オイラーのトーシェント関数 φ(n) は、1 ≤ k ≤ n かつ gcd(k, n) = 1 を満たす整数 k の個数を表します(オイラーの φ 関数とも呼ばれます)。たとえば 1, 2, 4, 5, 7, 8 の 6 個は 9 と 1 以外の公約数をもたないので、φ(9) = 6 です。
eulers_totient(n) を実装してください。
n は最大 10^12 なので、k を 1 つずつ数えていては間に合いません。代わりに、n を割り切る相異なる素数 p すべてについて n に (1 − 1/p) を掛けていく、積の公式 φ(n) = n × Π(1 − 1/p) を使いましょう。整数のまま n / p × (p − 1) と計算すれば、分数を使わずに済みます。
入力
n: 正の整数。
出力
φ(n) を返してください。定義より φ(1) = 1 です。
制約
1 ≤ n ≤ 10^12
例
入力:
n = 36
期待される出力:
expected = 12
入力:
long long n = 36;
期待される出力:
long long expected = 12;
入力:
long n = 36;
期待される出力:
long expected = 12;
解説
36 = 2² × 3² なので、φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × 1/2 × 2/3 = 12 です。
入力:
n = 13
期待される出力:
expected = 12
入力:
long long n = 13;
期待される出力:
long long expected = 12;
入力:
long n = 13;
期待される出力:
long expected = 12;
解説
13 は素数なので、1 から 12 までのすべての k が 13 と互いに素で、φ(13) = 12 です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
√n までの試し割りで n を素因数分解しましょう。
ヒント 2
相異なる素数 p ごとに、結果を「結果 / p × (p − 1)」で置き換えます。先に割ることで値が大きくなりすぎません。
ヒント 3
ループのあとに 1 より大きい因数が残っていれば、それも素数です。
目安の計算量
時間 O(√n)、追加メモリ O(1)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。