C1247 [JSOI2013]丢番图

内存限制:256 MB 时间限制:1000 ms

题目描述

丢番图是亚历山大时期埃及著名的数学家。他是最早研究整数系数不定方程的数学家之一。

为了纪念他,这些方程一般被称作丢番图方程。最著名的丢番图方程之一是 $x^N+y^N=z^N$。费马提出,对于 $N>2$,$x,y,z$ 没有正整数解。这被称为“费马大定理”,它的证明直到最近才被安德鲁·怀尔斯(AndrewWiles)证明。

考虑如下的丢番图方程:

$1/x+1/y=1/n(x,y,n \in N^+)$ (1)

小 G 对下面这个问题十分感兴趣:对于一个给定的正整数 $n$,有多少种本质不同的解满足方程(1)?例如 $n=4$,有三种本质不同 $(x≤y)$ 的解:

$1/5+1/20=1/4$

$1/6+1/12=1/4$

$1/8+1/8=1/4$

显然,对于更大的 $n$,没有意义去列举所有本质不同的解。你能否帮助小 G 快速地求出对于给定 $n$,满足方程(1)的本质不同的解的个数?

输入格式

一行,仅一个整数 $n(1 \le N \le 10^{14})$

输出

一行,输出对于给定整数 $n$,满足方程(1)的本质不同的解的个数。

样例

样例输入 1

4

样例输出 1

3

提示