問題一覧 > 通常問題

No.3691 Calculate Mu Sum

レベル : / AI推定難易度 : 800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 59
作問者 : Unbakedbread / テスター : Tamiji153
お気に入りにしたユーザー ProblemId : 13821 / 自分の提出
問題文最終更新日: 2026-08-28 01:45:04
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
μ関数入門コース (順位表) の他の問題:

Problem Statement

You are given a positive integer $N$.

Find the sum of $\mu(k)$ over all integers $k$ between $1$ and $N$, inclusive.

What is $\mu(N)$? (click to expand) For a positive integer $N$, the value of $\mu(N)$ is defined as follows.
  • If $N=1$, then $\mu(N)=1$.
  • If $N$ is divisible by the square of some prime, then $\mu(N)=0$.
  • If $N$ is equal to the product of $K$ distinct primes, then $\mu(N)=(-1)^K$.

Constraints

  • $N$ is an integer between $1$ and $10^7$, inclusive.

Input

$N$

Output

Output the answer.

Sample

Sample 1
Input
6
Output
-1

$\mu(1)+\mu(2)+\mu(3)+\mu(4)+\mu(5)+\mu(6)=1-1-1+0-1+1=-1$.

Sample 2
Input
31
Output
-4
Sample 3
Input
10000000
Output
1037

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