• [1678] 移动

  • 时间限制: 8000 ms　内存限制: 262144 K
  • 问题描述

  • 鶸菜Lweleth爱打音游，现在有n个按钮，每个按钮与起点距离即它的编号，现在他决定以移动间隔s(s<=n)来进行移动点击2个按钮（s可以是任意数，当然他尽可能选择更大的数）。每次他都要从0开始移动，点击到一个按钮后瞬间回到原点0。

    这样两次动作记作一组，一组中不能更换移动间隔s，完成后他可再次决定s。

    现在他想知道，移动间隔s为素数且不同的方案数有多少种。

  • 输入
  • 第一行输入 $N (1<= N <= 1e7)$
  • 输出
  • 输出一个数
  • 样例输入
  • 4
12
  • 样例输出
  • 4
39
  • 提示
  • 第一组样例中n=4 他可以选择s=2，3 那么有四种方案：
1.第一次点击第2个按钮 第二次点击第2个按钮
2.第一次点击第2个按钮 第二次点击第4个按钮
3.第一次点击第3个按钮 第二次点击第3个按钮
4.第一次点击第4个按钮 第二次点击第2个按钮
他无法两次都点击第4按钮，因为他会尽可能选择大的移动间隔，即s=4 而4并不是素数。
  • 来源
  • 本站或者转载
  • 操作

显示春菜