BZOJ-2226: [Spoj 5971] LCMSum

Description

多组询问 1 <= T <= 300000 1 <= n <= 1000000 求

推式子！

=
=
=
=
=
=
=
=
=
=
发现n为奇数的时候好像有整除的问题，那么我们把1提取出来。
=
来吧！两个奇性函数的乘积和的卷积显然积性，快筛！！！然后乱搞就好了啊。还不用取mod，不需要考虑整除！！！
然而听ckh说好像这是一个公式吧？？？
设
当x!=1的时候额。。。我能说些什么呢？？？QwQ

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
ll phi[1001000],pri[501000],cnt,yz[1001000];;
bool v[1001000];
void initialize()
{
    phi[1]=1; ll i,j; 
    for(i=2;i<=1000000;++i)
    {
        if(!v[i]) pri[++cnt]=i,phi[i]=i*(i-1)+1,yz[i]=i;
        for(j=1;i*pri[j]<=1000000&&j<=cnt;++j)
        {
            v[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                yz[i*pri[j]]=yz[i]*pri[j];
                phi[i*pri[j]]=
                    yz[i*pri[j]]==i*pri[j] ? 
                    phi[i]+i*i*pri[j]*(pri[j]-1) : 
                    phi[i*pri[j]/yz[i*pri[j]]]*phi[yz[i*pri[j]]];
                break;
            }
            phi[i*pri[j]]=phi[i]*(pri[j]*(pri[j]-1)+1);
            yz[i*pri[j]]=pri[j];
        }
    }
}
int main()
{
    int t,n; scanf("%d",&t); initialize();
    while(t--)
    {
        scanf("%d",&n);
        printf("%llu\n",n*(phi[n]-1)/2+n);
    }
    return 0;
}