題目：HDU2588

?

題意大概：給定N,M(2<=N<=1000000000, 1<=M<=N), 求1<=X<=N 且gcd(X,N)>=M的個數。

解法：數據量太大，用常規方法做是行不通的。后來看了別人的解題報告說，先找出N的約數x，

????????? 并且gcd（x，N）>= M，結果為所有N/x的歐拉函數之和。

???????? ?因為x是Ｎ的約數，所以ｇｃｄ（ｘ，Ｎ）＝ｘ >= M；

　　　設ｙ＝Ｎ／ｘ，ｙ的歐拉函數為小于ｙ且與ｙ互質的數的個數。

　　　設與ｙ互質的的數為ｐ１，ｐ２，ｐ３，…，ｐ４

　　　那么ｇｃｄ（ｘ* pi，N）= x >= M。

????????? 也就是說只要找出所有符合要求的y的歐拉函數之和就是答案了。

#include<stdio.h> #include<math.h> int Euler(int n) {if(n==1)return 1;int i=2,m=n,root=(int)sqrt(n);while(i<=root){if(m%i==0){n-=n/i;while(m%i==0)m/=i;root=(int)sqrt(m);}i++;}if(m!=1){n-=n/m;}return n; } int solve(int n,int m) {int nn = sqrt(n),ans=0;for(int i=1;i<=nn;i++){if(n%i) continue;if(i>=m&&i!=nn)ans += Euler(n/i);if(n/i>=m)ans += Euler(i);}return ans; } int main() {int n,t,m;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);printf("%d\n",solve(n,m));}return 0; }

總結

以上是生活随笔為你收集整理的HDU2588解析的全部內容，希望文章能夠幫你解決所遇到的問題。

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