题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=121873#problem/F
题目大意：给你一个数n，让你输出（i=1->n-1)(j=i+1->n)gcd(i,j）
思路分析：直接暴力做铁定超时，而且数据也不止一组，因此我们要考虑打表来做这一道题， 既然要打表，就要
寻找递推关系，手写一下，比较容易就可以找到递推关系，S[n]=S[n-1]+f[n]
f[n]=gcd(1,n)+gcd(2,n)+.......+gcd(n-1,n),现在问题就转化成了如何求f[n]，直接求目测超时，这一步就
比较奇妙，我们可以从约数开始入手，看约数为1.2.....分别有多少个数，数的个数刚好为phi[j/i]
代码：
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=+;
ll phi[maxn];
ll prime[maxn/];
ll s[maxn];
ll f[maxn];
bool check[maxn];
int tot;
void make_phi()
{
phi[]=;
memset(check,true,sizeof(check));
tot=;
for(ll i=;i<maxn;i++)
{
if(check[i])
{
prime[tot++]=i;
phi[i]=i-;
}
for(int j=;j<tot&&i*prime[j]<=maxn;j++)
{
check[i*prime[j]]=false;
if(i%prime[j]==)
{
phi[i*prime[j]]=phi[i]*prime[j];
}
else phi[i*prime[j]]=phi[i]*(prime[j]-);
}
}
}
void init()
{
memset(f,,sizeof(f));
for(int i=;i<maxn;i++)//打表求f[i]
{
for(int j=*i;j<=maxn;j+=i)
{
f[j]+=i*phi[j/i];
}
}
s[]=;
for(ll i=;i<maxn;i++)
{
s[i]=s[i-]+f[i];
}
}
int main()
{
ll n;
make_phi();
init();
while(scanf("%lld",&n)&&n)
{
printf("%lld\n",s[n]);
}
}