题目：给出n，求gcd(1,2)+gcd(1,3)+gcd(2,3)+gcd(1,4)+gcd(2,4)+gcd(3,4)+...+gcd(1,n)+gcd(2,n)+...+gcd(n-1,n)
此题和UVA 11426 一样，不过n的范围只有20000，但是最多有20000组数据。 当初我直接照搬UVA11426，结果超时，因为没有预处理所有的结果(那题n最多4000005，但最多只有100组数据)，该题数据太多了额。。。
思路：令sum(n)=gcd(1,n)+gcd(2,n)+...+gcd(n-1,n)，则所求结果ans(n)=sum(2)+sum(3)+...+sum(n)
只需求出sum(n)，就可以推出所有答案：ans(n)=ans(n-1)+sum(n)(我当时怎么就没想到呢，额。。。)。
接下来重点就是求sum(n)：
注意到所有gcd(x,n)都是n的约数，可以按照这个约数进行分类，用g(n,i)表示满足g(x,n)=i且x<n的正整数个数，
则sum(n)=sum{i*g(n,i)|i是n的约数}。注意到gcd(x,n)=i的充要条件是gcd(x/i,n/i)=1
(额，我是看到书上的这个提示，才想到怎么做的。。。)，因此满足条件的x/i有phi(n/i)个(欧拉函数)，说明g(n,i)=phi(n/i)。
由于时间限制，同素数筛选法，我们需要对于每个i枚举它的倍数n并更新sum(n)，这些都在预处理中完成。
#include <iostream> #include <stdio.h> #include <string.h> /* 数论题 题目：给出n，求gcd(1,2)+gcd(1,3)+gcd(2,3)+gcd(1,4)+gcd(2,4)+gcd(3,4)+...+gcd(1,n)+gcd(2,n)+...+gcd(n-1,n) 思路：令sum(n)=gcd(1,n)+gcd(2,n)+...+gcd(n-1,n)，则所求结果ans(n)=f(2)+f(3)+...+f(n) 只需求出f(n)，就可以推出所有答案：ans(n)=ans(n-1)+sum(n)(我当时怎么就没想到呢，额。。。)。 接下来重点就是求sum(n)： 注意到所有gcd(x,n)都是n的约数，可以按照这个约数进行分类，用g(n,i)表示满足g(x,n)=i且x<n的正整数个数， 则sum(n)=sum{i*g(n,i)|i是n的约数}。注意到gcd(x,n)=i的充要条件是gcd(x/i,n/i)=1 (额，我是看到书上的这个提示，才想到怎么做的。。。)，因此满足条件的x/i有phi(n/i)个(欧拉函数)，说明g(n,i)=phi(n/i)。 由于时间限制，同素数筛选法，我们需要对于每个i枚举它的倍数n并更新sum(n)，这些都在预处理中完成。 */ using namespace std; const int maxn=200005; int phi[maxn]; long long sum[maxn]; long long ans[maxn]; void init(){ memset(phi,0,sizeof(phi)); memset(sum,0,sizeof(sum)); memset(ans,0,sizeof(ans)); phi[1]=1; for(int i=2;i<maxn;i++){ if(!phi[i]){ for(int j=i;j<maxn;j+=i){ if(!phi[j]) phi[j]=j; phi[j]=phi[j]/i*(i-1); } } } long long i,j; for(i=2;i<maxn;i++){ for(j=1;i*j<maxn;j++){ /* //原来第二次循环j是从1~maxn，循环中加个if条件，预处理都运行很慢很慢，超时 if(i*j>=maxn) continue; */ sum[i*j]+=phi[i]*j; //n=i*j，j为n和x的公约数，类似于素数筛选法 } } /* //白书上的代码 for(int i=1;i<maxn;i++){ for(int n=i*2;n<maxn;n+=i) sum[n]+=i*phi[n/i]; } */ ans[2]=sum[2]; for(int i=3;i<maxn;i++){ ans[i]=ans[i-1]+sum[i]; //怎么都忘记可以利用前一项的结果啊！！！ } } int main() { init(); int n; long long result; while(scanf("%d",&n),n){ printf("%lld ",ans[n]); //UVA上，注意是lld } return 0; }