題目大意：給出一組n和k，求解滿足公式：gcd(n-a,n)*gcd(n-b,n)=n^k的(a,b)的對數，結果對(1e9+7)取模。

先證明：對于1<=x<=n，有gcd(n-x , n) =?gcd(x , n) 。

假設gcd(n-a , n) = x（1<=a<=n），則x是(n-a)和n的最大公約數，所以存在整數k1，k2（并且k1<k2，而且

gcd(k1,k2)=1即k1和k2沒有除1以外的公約數）使得n-a=k1*x，n=k2*x；那么a=n-k1*x=k2*x-k1*x=(k2-k1)*x，則

gcd(a,n)=gcd((k2-k1)*x,n)=gcd((k2-k1)*x,k2*x)。那么gcd((k2-k1)*x,k2*x)是否等于x呢？？？

因為k1與k2沒有除1以外的公約數，所以對任意的i（i>1）都有k2!=k1*i，則（k2-k1）與k2沒有除1以外的公約數。

所以gcd(a,n)=gcd((k2-k1)*x,k2*x)=x=gcd(n-a , n)，同理gcd(b,n)=gcd(n-b,n)

解題思路：gcd(n-a,n)*gcd(n-b,n)=n^k可以化為gcd(a,n)*gcd(b,n)=n^k。

對于任意的gcd(x,y)<=max(x,y)，則對于公式：gcd(a,n)*gcd(b,n)=n^k，

因為1<=a,b<=n，所有我們有gcd(a,n)<=n，gcd(b,n)<=n。所以gcd(a,n)*gcd(b,n)<=n^2，則

當n=1時，原公式只有1解；

當k>2時，原公式無解；

當k=2時，只有a=b=n時，gcd(a,n)=n，gcd(b,n)=n，gcd(a,n)*gcd(b,n)=n^2，即原公式只有1解；

當k=1時，就是求gcd(a,n)*gcd(b,n)=n，如果gcd(a,n)=x，則gcd(b,n)=n/x，這里只要枚舉x，求n/x即可。x是a和n的最

大公約數，那么x就是n的因數，因此枚舉n的因數就可以了。對于每一個x可能會有多個a（1<=a<=n）存在，使得

gcd(a,n)=x，假設存在ma個；那么對于每一個n/x，同樣會有多個b（1<=b<=n）存在，使得gcd(b,n)=n/x，假設存在

mb個（對于ma，mb的求解可以用歐拉函數求解？？？？？）。那么對于一個x，如果x*x!=n，那么就存在2*ma*mb

對結果，如果x*x==n，那么就存在ma*mb對結果。

感覺對這些數論的定理公式還是不能夠很靈活的運用。。。多多刷題

AC:

#include <cstdio> #include <iostream> #define mod 1000000007 using namespace std; typedef __int64 LL; LL n,k; //歐拉函數 LL euler(LL x) {LL i,res=x;for(i=2;i*i<=x;i++){if(x%i==0){res=res/i*(i-1);while(x%i==0)x=x/i;}}if(x>1)res=res/x*(x-1);return res; }int main() {LL i,sum;while(scanf("%I64d%I64d",&n,&k)!=EOF){if(n==1){printf("1\n");continue;}if(k>2){printf("0\n");continue;}if(k==2){printf("1\n");}else//當k=1時{sum=0;//枚舉n的因數for(i=1;i*i<=n;i++){if(n%i==0){if(i*i==n)sum+=euler(n/i)*euler(i);elsesum+=2*euler(n/i)*euler(i);sum%=mod;}}printf("%I64d\n",sum);}}return 0; }

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的hdu 4983（欧拉函数）的全部內容，希望文章能夠幫你解決所遇到的問題。

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