Description

丟番圖 是亞歷山大時期埃及著名的數學家。他是最早研究整數系數不定方程的數學家之一。

為了紀念他，這些方程一般被稱作丟番圖方程。最著名的丟番圖方程之一是 xn+yn=zn 。費馬

提出，對于 n≥2 ， xn+yn=zn 沒有正整數解。這被稱為“費馬大定理”，它的證明直到最近才被安德

魯·懷爾斯（Andrew Wiles）證明。

考慮如下的丟番圖方程：

1x+1y=1n(x，y，n∈N?)

小G 對下面這個問題十分感興趣：對于一個給定的正整數n ，有多少種本質不同的解滿足方

程（1）？例如 n=4 ，有三種本質不同 (x≤y) 的解：

15+120=14

16+112=14

18+18=14

Input

顯然，對于更大的n ，沒有意義去列舉所有本質不同的解。你能否幫助小G 快速地求出對于給定n，滿足方程（1）的本質不同的解的個數？

Output

一行，僅一個整數n（ 1≤n≤1014 ）。

Sample Input

4

Sample Output

3

Data Constraint

對于 30% 的數據， n≤105

對于 50% 的數據， n≤231

對于 100% 的數據， n≤1014

Solution

• 這題的解法十分巧妙，推導過程十分機智啊！（贊口不絕~）

• 對于方程：

  1x+1y=1n

• 去分母得：

  xy=xn+yn

• 移項得：

  xy?xn?yn=0

• 兩邊同時加 n2 得：

  xy?xn?yn+n2=n2

• 左邊因式分解得：

  (x?n)(y?n)=n2

• 所以，答案就是 n2 的 約數個數/2（向上取整）！！！

• 又根據定理可得：一個數的約數個數等于所有質因數的 次數+1 的乘積

• 那么就這樣邊約邊求即可！時間復雜度 O(N??√)！

Code

#include<cstdio> #include<cmath> using namespace std; long long n; int sum; int main() {scanf("%lld",&n);long long m=sqrt(n),ans=1;for(int i=2;i<=m;i++)if(!(n%i)){for(sum=0;!(n%i);sum++) n/=i;ans*=sum<<1|1;if(n==1) break;}if(n>1) ans*=3;printf("%lld",(ans+1)>>1);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 3158. 【JSOI2013】丢番图的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。