Processing math: 100%
编程题
                丢番图

题目描述

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

为了纪念他,这些方程一般被称作丢番图方程。最著名的丢番图方程之一是

xn+yn=zn

费马提出,对于 n>2, x,y,z 没有正整数解。这被称为“费马大定理”,它的证明直到最近才被安德鲁·怀尔斯(AndrewWiles)证明。

考虑如下的丢番图方程:

$$\frac{1}{x}+\frac{1}{y}=\frac{1}{n},(x,y,n\in~N^+)$$

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

$\frac{1}{5}+\frac{1}{20}=\frac{1}{4}$

$\frac{1}{6}+\frac{1}{12}=\frac{1}{4}$

$\frac{1}{8}+\frac{1}{8}=\frac{1}{4}$

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

输入描述

输入一行,仅一个整数 n

其中,1n1014

输出描述

输出一行一个整数代表答案。

输入输出样例

示例 1

>输入

4

>输出

3
查看答案
赣ICP备20007335号-2