1876:满足条件的整数和
文件提交:无需freopen
内存限制:128 MB
时间限制:1.000 S
评测方式:普通裁判
命题人:
提交:2
解决:2
题目描述
蒜头君在学习质因数分解时,遇到这样一个定义:
已知一个正整数 $n$ 可以由两个质数 $p$ 和 $q$ 相乘得到,即 $n=p \times q$
蒜头君根据质因数分解的理论得出结论:如果令 $p\le q$,则 $p,q$ 的值是唯一的。例如: $n=14$, 则 $p=2,q=7$
已知两个质数 $p$ 和 $q$,它们的乘积为 $n=p\times q$
现在告诉你 $n$ 的值,你的任务是计算所有同时满足以下两个条件的正整数 $e$ 的和。
- 条件一:$1\le e\le (p-1)\times (q-1)$
- 条件二:$e$ 是 $(p-1)\times (q-1)$ 的因子
输入
输入一个正整数 $n(4\le n\le 10^{12})$,保证 $n$ 等于两个质数 $p$ 和 $q$ 的乘积。
输出
输出共一行,一个正整数,表示所有满足条件的 $e$ 的和。
样例输入-1 复制
4
样例输出-1 复制
1
样例输入-2 复制
6
样例输出-2 复制
3
提示
样例解释1:$n=4=2\times 2$, 所以 $p=2,q=2$
$(p-1)\times (q-1) = (2-1)\times (2-1) = 1$
正整数 $1$ 的因子有 $1$,所以答案为:$1$
样例解释2:$n=6=2\times 3$,所以 $p=2,q=3$
$(p-1)\times (q-1)=(2-1)\times (3-1) = 2$
正整数 $2$ 的因子有 $1,2$,所以答案为:$1+2=3$