← 返回题目列表

AtCoder · xmascon19_d

D. (-1)^f(n) 之和

中文机器翻译题面 查看原题

配点: 100 点

Xmas Contest 2013 问题 G 的黑兔说:“10^9 呀(笑)只有符号(笑)”

問題文

正整数 n , 定义f(n) 该值应乘以 n 所持有的素因数数量(包含重复)。例如,200 = 2^3 \times 5^2 因此,f(200) = 5 变为。

正整数 N ,所以\sum_{n=1}^N (-1)^{f(n)} 。

制約

  • 1 \le N \le 10^{11}.

部分点

  • N \le 10^{10} 的数据集,45 点。 如果所有满足
  • 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 输出(小于 55 点。 如果所有满足

入力

N

出力

\sum_{n=1}^N (-1)^{f(n)} 的值 1 行输出。 没有


入力例 1

6

出力例 1

0

f(1) = 0,f(2) = 1,f(3) = 1,f(4) = 2,f(5) = 1,f(6) = 2 因此,答案是 (-1)^0 + (-1)^1 + (-1)^1 + (-1)^2 + (-1)^1 + (-1)^2 = 0 。


入力例 2

2019

出力例 2

-25

入力例 3

906150257

出力例 3

1