题目：求sum(gcd(i,j)),(1<=i
题解：我们设答案为ans[n],ans[n]=ans[n-1]+gcd(1,n)+gcd(2,n)+...+gcd(n-1,n)；接下来的问题是如何求gcd(1,n)+gcd(2,n)+...+gcd(n-1,n)；
设g[n]=gcd(1,n)+gcd(2,n)+...+gcd(n-1,n); 设p(i)表示目前为止与n的gcd为i的数有几个？则g[n]=sum(p[i])(1<=i<=n)；
假设gcd(x,n)=i，那么显然gcd(x/i,n/i)=1,所以p[i]即为phi(n/i)的值。
所以我们只需预处理出phi的值就可以了。
程序：
#include
#include
#include
#include
#include
#define maxn 4000009
using namespace std;
typedef long long ll;
ll phi[maxn],g[maxn],f[maxn];
int n;
int main()
{
scanf("%d",&n);
for (int i=1;i0;
phi[1]=1;
for (int i=2;i)
{
if (phi[i]) continue;
for (int j=i;ji)
{
if (!phi[j]) phi[j]=j;
phi[j]-=phi[j]/i;
}
}
for (int i=1;i)
for (int j=i+i;ji)
g[j]+=phi[j/i]*i;
f[2]=g[2];
for (int i=3;i1]+g[i];
while (n)
{
printf("%lld\n",f[n]);
scanf("%d",&n);
}
return 0;
}