本文主要是介绍GCD HDU - 2588，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
对于一个数n 在比它小的数中 除了他的因子 其他数和n的gcd均为1 所有符合题意的数x肯定是n的某个因子的倍数
所以只用看n的所有因子 假设有一个n的因子p大于m 就看（n/p）的欧拉函数值是多少 累加
至于为什么要求（n/p）的欧拉函数 这是为了解决”冲突“ 对于n的因子p和一个与（n/p）不互素的k k*p就会变成n的其他因子或其他因子的倍数 这里需要仔细想想
#include<bits/stdc++.h>
using namespace std;int geteular(int n)
{int ans,i;ans=n;for(i=2;i*i<=n;i++){if(n%i==0){ans-=ans/i;while(n%i==0){n/=i;}}}if(n>1) ans-=ans/n;return ans;
}int main()
{int t,n,m,i,ans;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);ans=0;for(i=1;i*i<=n;i++){if(i*i<n){if(n%i==0){if(i>=m) ans+=geteular(n/i);if(n/i>=m) ans+=geteular(i);}}else{if(i>=m) ans+=geteular(i);}}printf("%d\n",ans);}return 0;
}
这篇关于GCD HDU - 2588的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
