すべてのチャレンジ
中級 0件解決済み 正答率0%

オイラーのトーシェント関数

1 から n までの整数のうち、n と互いに素なものの個数を求めます。

このチャレンジで学べること

  • n の相異なる素因数を求める
  • 整数だけを使って φ(n) = n × Π(1 − 1/p) を計算する
  • n = 1 や n が素数の場合に対応する

問題

原文(英語)を表示

オイラーのトーシェント関数 φ(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

例

例 1
入力:
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 です。

例 2
入力:
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用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。