Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom10月前

09/11
13:54
数学相关

[bzoj 4459] [Jsoi2013]丢番图

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 丢番图是亚历山大时期埃及著名的数学家。他是最早研究整数系数不定方程的数学家之一。
为了纪念他,这些方程一般被称作丢番图方程。最著名的丢番图方程之一是x^N+y^n=z^N。费马提出,对于N>2,x,y,z没有正整数解。这被称为“费马大定理”,它的证明直到最近才被安德鲁·怀尔斯(AndrewWiles)证明。
考虑如下的丢番图方程:
1/x+1/y=1/n(x,y,n属于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)的本质不同的解的个数?

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

一行,仅一个整数n(1<=N<=10^14)

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

4

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

3

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

1/x+1/y=1/n

xn+yn=xy

xy-xn-yn+n^2=n^2

(x-n)(y-n)=n^2

答案就是n^2的约数个数/2,一个数的约数个数等于所有质因数的次数+1的乘积。

c++:

pascal:

 

[bzoj 4459] [Jsoi2013]丢番图