题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2588

GCD

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 218    Accepted Submission(s): 66

3
1 1
10 2
10000 72

1
6
260

这个题数据量比较大，所以暴力是肯定要超时的。故，我们需要思考一些算法来优化我们的程序

我们可以在sqrt(n)的时间内找到n的所有约数，而这些约数和n的最大公约数就是这个约数本身

我们可以寻找x>=m且x是n的约数，最后答案就是每一个大于m的约数x

ans=sigma(eular(n/x))

可以大概的说一下为什么这样处理

因为对于x的倍数和n取最大公约数，则其值完全可能大于x。

那么可以证明出，必然在m<=k*x<=n之间一定存在eular(n/x)个数与n的最大公约数是x

我的代码：
#include<stdio.h><br /> #include<algorithm><br /> #include<string.h><br /> #include<math.h></p> <p>using namespace std;</p> <p>int a[40000];</p> <p>int eular(int n)<br /> {<br /> int ret=1,i;<br /> for(i=2;i*i<=n;i++)<br /> {<br /> if(n%i==0)<br /> {<br /> n=n/i;<br /> ret=ret*(i-1);<br /> while(n%i==0)<br /> {<br /> n=n/i;<br /> ret=ret*i;<br /> }<br /> }<br /> if(n==1)<br /> break;<br /> }<br /> if(n>1)<br /> ret=ret*(n-1);<br /> return ret;<br /> }</p> <p>int main()<br /> {<br /> int i,num,n,m,T,ans;<br /> scanf("%d",&T);<br /> while(T--)<br /> {<br /> num=0,ans=0;<br /> scanf("%d%d",&n,&m);<br /> for(i=1;i*i<n;i++)<br /> {<br /> if(n%i==0)<br /> {<br /> a[num++]=i;<br /> a[num++]=n/i;<br /> }<br /> }<br /> if(i*i==n)<br /> a[num++]=i;<br /> sort(a,a+num);<br /> for(i=0;i<num;i++)<br /> {<br /> if(a[i]>=m)<br /> ans=ans+eular(n/a[i]);<br /> }<br /> printf("%d/n",ans);<br /> }<br /> return 0;<br /> }