← 返回题目列表

Codeforces · 542/D

D. 超级英雄的工作

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

成为超级英雄很难。抵抗数学出色的超级恶棍的难度要加倍。假设你是一个普通的蝙蝠侠,生活在一个普通的哥谭市。你的敌人小丑在市政府大楼里埋下了地雷,你只有几分钟的时间来抵消攻击。为此,您应该在炸弹控制面板上输入取消代码。

然而,那个疯子决定给你一个提示。今天早上,市长在枕头下发现了一张扑克牌。卡片上写着一行字:

$$J(x) = \sum_{\substack{1 \leq k \leq x \\ k | x \\ \gcd(k, x/k) = 1}} k$$

炸弹上有一个注释,写着“J(x) = A”,其中 A 是某个正整数。你怀疑取消代码是某个满足方程 J(x) = A 的整数 x。现在为了决定是否应该中和炸弹还是逃命,你必须计算有多少个不同的正整数 x 满足这个方程。

输入

输入的单行包含单个整数 A (1 ≤ A ≤ 1012)。

输出

打印方程 J(x) = A 的解数。

示例

输入 #1

3

输出 #1

1

输入 #2

24

输出 #2

3

注意

记录 x|n 表示数字 n 除数字 x。

$$\gcd(a,b)$$ 定义为同时整除 a 和 b 的最大正整数。

在第一个样本测试中,x 的唯一合适值为 2。则 J(2) = 1 + 2。

在第二个示例中测试 x 的以下值匹配:

- x = 14,J(14) = 1 + 2 + 7 + 14 = 24
- x = 15,J(15) = 1 + 3 + 5 + 15 = 24
- x = 23, J(23) = 1 + 23 = 24