#ABC161F. Division or Subtraction
Division or Subtraction
题目描述
Given is a positive integer .
We will choose an integer between and (inclusive), then we will repeat the operation below until becomes less than .
- Operation: if divides , replace with ; otherwise, replace with .
In how many choices of will become in the end?
给定正整数 。
我们将在 和 之间(含)选择一个整数 ,然后重复下面的操作,直到 小于 。
- 操作:如果 除以 ,则用 替换 ;否则,用 替换 。
在 的多少种选择中, 最后会变成 ?
输入格式
输入内容按以下格式标准输入:
输出格式
打印 中 最后变成 的选项数。
样例 #1
样例输入 #1
6
样例输出 #1
3
样例 #2
样例输入 #2
3141
样例输出 #2
13
样例 #3
样例输入 #3
314159265358
样例输出 #3
9
说明
数据规模与约定
- 是整数。
样例 解释
有三种 的选择,其中 最终会变成 : 、 和 。
在每一个选择中, 都会发生如下变化:
- 当 :
- 当 :
- 当 :