BZOJ-2401: 陶陶的难题I

Description

求
n<=10^6 多组询问 t<=10^5

我们可以递推答案：
那么对于，这个是可以快筛的，详见：BZOJ-2226
快筛+递推即可 时间复杂度O(n+T)
中精度差评

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=100000000000000ll;
struct precision
{
    ll a,b;
    precision(){a=b=0;}
    void operator += (const ll z)
    {
        a+=(b+z)/mod;
        b=(b+z)%mod;
    }
    void operator += (const precision z)
    {
        a+=z.a;
        (b+z.b>=mod) ? a++,b=b+z.b-mod : b+=z.b;
    }
    void print()
    {
        if(a) printf("%lld%014lld\n",a,b);
        else printf("%lld\n",b);
    }
}ans[1001000];
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];
        }
    }
    for(int i=1;i<=1000000;++i)
    {
        ans[i]=ans[i-1];
        ans[i]+=(ll)i*(phi[i]-1)+i;
    }
}
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2) ? EOF:*p1++;
}
inline void read(int &x)
{
    x=0; char ch=nc();
    while(!isdigit(ch)) ch=nc();
    while(isdigit(ch)) x=x*10+ch-'0',ch=nc();
}
int main()
{
    initialize(); int t,n; read(t); 
    while(t--)
    {
        read(n);
        ans[n].print();
    }
    fclose(stdin);
    return 0;
}