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

终于学杜教筛了wakkk！！！

这个普及度极高的东西网上都有，就不赘述了。。。

头铁用 map ，然后觉得很卡常。。。

果然没过。。。。卡了半天都过不去。。。

搞了半天才发现原来两个一起算就好了（当时刚学会杜教筛膨胀的以为自己可以*天。。。。。就想都没想两个分开算的。。。）

这可是个 2 的巨大常数啊！！！

不知道为什么 map 跑的贼快233

#include
    
     using namespace std;const int N = 2500010;struct lpl{    long long PHI, MU;};bool not_prime[N];long long n, tot, prime[N], phi[N], mu[N];map
     
       LPL;inline void prepare(){    mu[1] = 1; phi[1] = 1;    for(register int i = 2; i < N; ++i){        if(!not_prime[i]){            prime[++tot] = i; mu[i] = -1; phi[i] = i - 1;        }        for(register int now, j = 1; prime[j] * i < N; ++j){            now = prime[j] * i; not_prime[now] = true;            if(i % prime[j] == 0){                mu[now] = 0; phi[now] = prime[j] * phi[i];                break;            }            mu[now] = -mu[i]; phi[now] = phi[i] * (prime[j] - 1);        }    }    for(register int i = 2; i < N; ++i) phi[i] += phi[i - 1], mu[i] += mu[i - 1];}lpl Query(long long t){       lpl ld;    if(t < N){ld.PHI = phi[t]; ld.MU = mu[t]; return ld;}    if(LPL[t].PHI) return LPL[t];    long long last; long long ret1 = (t * (t + 1)) >> 1, ret2 = 1;    for(register long long i = 2; i <= t; i = last + 1){        last = min(t, t / (t / i)); ld = Query(t / i);        ret1 -= (last - i + 1) * ld.PHI; ret2 -= (last - i + 1) * ld.MU;    }    ld.PHI = ret1; ld.MU = ret2; LPL[t] = ld;     return ld;}int main(){    prepare();    int T; lpl ld; scanf("%d", &T);    while(T--){        scanf("%lld", &n); ld = Query(n);        printf("%lld %lld\n", ld.PHI, ld.MU);       }    return 0;}