問題一覧 > 通常問題

No.3691 Calculate Mu Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 37
作問者 : Unbakedbread / テスター : Tamiji153
お気に入りにしたユーザー ProblemId : 13821 / 自分の提出
問題文最終更新日: 2026-08-28 01:45:04
μ関数入門コース (順位表) の他の問題:

問題文

正整数 $N$ が与えられます。

$1$ 以上 $N$ 以下の整数 $k$ 全てに対する $\mu(k)$ の総和を求めてください。

$\mu(N)$ とは（クリックで開く） 正整数 $N$ に対して、 $\mu(N)$の値は以下のように定義されます。
  • $N=1$ のとき、 $\mu(N)=1$
  • $N$ がある素数の平方で割り切れるとき、 $\mu(N)=0$
  • $N$ が $K$ 個の相異なる素数の積に等しいとき、 $\mu(N)=(-1)^K$

制約

  • $N$ は $1$ 以上 $10^7$ 以下の整数

入力

$N$

出力

答えを出力せよ。

サンプル

サンプル1
入力
6
出力
-1

$\mu(1)+\mu(2)+\mu(3)+\mu(4)+\mu(5)+\mu(6)=1-1-1+0-1+1=-1$ です。

サンプル2
入力
31
出力
-4
サンプル3
入力
10000000
出力
1037

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