問題一覧 > 通常問題

No.1322 Totient Bound

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 : chocorusk / テスター : noimi
4 ProblemId : 5614 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-12-12 23:41:33

問題文

正の整数 n に対し、1 以上 n 以下の整数のうち n と互いに素なものの個数を φ(n) と表します。

φ(x)≤N を満たす正の整数 x の個数を求めてください。この問題の制約下で、答えは有限であることが示せます。

入力

N

  • 1≤N≤1010
  • N は整数である。

出力

答えを出力してください。

サンプル

サンプル1
入力
4
出力
9

x=1,2,…,12 に対する φ(x) の値は順に 1,1,2,2,4,2,6,4,6,4,10,4 となります。x>12 のときは φ(x)>4 であることが示せるので、φ(x)≤4 を満たす正の整数 x は 1,2,3,4,5,6,8,10,12 の 9 個です。

サンプル2
入力
9
出力
18

サンプル3
入力
334
出力
643

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。