uva11424:
题目：给出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 <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include<iostream>
using namespace std;
int e[];
long long sum[],ans[];
int n;
void deal(){
memset(e,,sizeof(e));
e[]=;
for(int i=;i<;i++){
if(!e[i]){
for(int j=i;j<;j+=i){
if(!e[j])
e[j]=j;
e[j]=e[j]/i*(i-);
}
}
}
}
long long solve(){
deal();
memset(ans,,sizeof(ans));
memset(sum,,sizeof(sum));
long long i,j;
for( i=;i<=;i++)
for( j=*i;j<=;j+=i)
sum[j]+=i*e[j/i];
ans[]=sum[];
for(int i=;i<=;i++)
ans[i]=ans[i-]+sum[i];
}
int main(){
solve();
while(~scanf("%d",&n)&&n)
printf("%lld\n",ans[n]); }