bzoj 3944: Sum — 杜教筛

3944: Sum

Time Limit: 10 Sec  Memory Limit: 128 MB

Description

Input

一共T+1行

第1行为数据组数T(T<=10)

第2~T+1行每行一个非负整数N，代表一组询问

Output

一共T行，每行两个用空格分隔的数ans1,ans2

Sample Input

6
1
2
8
13
30
2333

Sample Output

1 1
2 0
22 -2
58 -3
278 -3
1655470 2

HINT

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define N 5000555 
ll t,tot,pri[N],mu[N];
ll phi[N],tp;
bool vs[N];
map<ll,pair<ll,ll> >m;
void sol(ll n,ll &ans1,ll &ans2)
{
    if(n<N){ans1=phi[n];ans2=mu[n];return;}
    if(m.count(n)){ans1=m[n].first;ans2=m[n].second;return;}
    ans1=(ll)n*(n+1)/2;ans2=1;
    ll last;
    for(ll i=2;i<=n;i=last+1)
    {
        last=n/(n/i);
        ll t1=0,t2=0;
        sol(n/i,t1,t2);
        ans1-=t1*(last-i+1);
        ans2-=t2*(last-i+1);
    }
    m[n]=make_pair(ans1,ans2);
}
int main()
{
    mu[1]=phi[1]=1;
    for(ll i=2;i<N;i++)
    {
        if(!vs[i])
        {
            pri[++tot]=i;
            mu[i]=-1;phi[i]=i-1;
        }
        for(ll j=1;j<=tot;j++)
        {
            tp=i*pri[j];
            if(tp>N) break;
            vs[tp]=1;
            if(i%pri[j]==0)
            {
                phi[tp]=phi[i]*pri[j];
                mu[tp]=0; break;
            }
            mu[tp]=-mu[i];
            phi[tp]=phi[i]*(pri[j]-1);
        }
        phi[i]+=phi[i-1];mu[i]+=mu[i-1];
    }
    scanf("%lld",&t);
    ll n;
    while(t--)
    {
        scanf("%lld",&n);
        if(!n){puts("0 0");continue;}
        ll ans1=0,ans2=0;
        sol(n,ans1,ans2);
        printf("%lld %lld\n",ans1,ans2);
    }
    return 0;
}