题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2582
题解：
打表找规律
先暴力打表求c，gcd，f。
运行下面这个程序

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
LL c[200][200];
LL GCD[50],sum[50];

void init()
{
    for(int i=1;i<=30;i++) c[i][0]=c[i][i]=1;
    for(int i=2;i<=30;i++)
        for(int j=1;j<=i;j++)
            c[i][j]=c[i-1][j]+c[i-1][j-1];
// for(int i=1;i<=30;i++)
// {
// for(int j=0;j<=i;j++) cout<<c[i][j]<<" ";
// cout<<endl;
// }
}

LL gcd(LL x,LL y)
{
    return (!y)?x:gcd(y,x%y);
}

void calc(LL x)
{
    LL tmp=c[x][1];
    for(int i=1;i<x;i++)
        tmp=gcd(c[x][i],tmp);
    GCD[x]=tmp; 
}

int main()
{
    init();
    for(LL i=3;i<=30;i++)
        {
            calc(i);
            sum[i]=sum[i-1]+GCD[i];
        }
    for(int i=3;i<=30;i++) cout<<GCD[i]<<" ";
    cout<<endl<<endl;
    for(int i=3;i<=30;i++) cout<<sum[i]<<" ";
    cout<<endl;
}

发现gcd数组是有规律的，对于gcd【i】

  1. i是质数，gcd【i】= i；
  2. 对于一个质数p，有 <nobr> i=pk(k≠1) </nobr>，gcd【i】= p；
  3. 其余数字gcd【i】= 1；

首先筛出素数，再枚举素数的幂次赋值，其余赋初值1
求一个前缀和即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;

LL gcd[1000010];
int prime[1000010],cnt;
unsigned long long f[1000010];
void init()
{
    for(int i=2;i<=1000000;i++)
        if(!gcd[i])
        {
            gcd[i]=i;
            prime[++cnt]=i;
            for(int j=i+i;j<=1000000;j+=i)
                gcd[j]=1;
        }
    LL tmp,k;
    for(int i=1;i<=cnt;i++)
    {
        tmp=prime[i];
        while(tmp*prime[i]<=1000000) {tmp*=prime[i];gcd[tmp]=prime[i];}     
    }
    for(int i=3;i<=1000000;i++)
        f[i]=f[i-1]+gcd[i];
}

int main()
{
    int n;
    init();
    while(~scanf("%d",&n))
        printf("%lld\n",f[n]);
    return 0;    
}