bzoj 3944 Sum 杜教篩

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

不過這題裡ϕ的字首和我記為了S，待會兒看代碼可能要注意。

莫比烏斯函數剛看不久，性質還記得幾個，

那麼這個就有用了：

∑d|iμ(d)=x

當i=1，x=1；i>1，x=0

那麼同樣的套路，令M(n)=∑ni=1μ(i)

那麼推導如下：

∑i=1n∑d|iμ(d)=1=∑k=1n∑i=1⌊n/k⌋μ(i)//重要步驟，仔細體會=∑k=1nM(⌊n/k⌋)是以∑k=1nM(⌊n/k⌋)=M(n)+∑k=2nM(⌊n/k⌋)=1M(n)=1−∑k=2nM(⌊n/k⌋)

然後記憶化搜尋即可，O(n23)。

由于n很大，是以要用map或者哈希的方法來存。

map強行多一個log。。于是我就光榮被卡。。

後面看到一些題解用map過了，隻是增大了預處理的量，

想想覺得線性篩真的不爛，是以調到了250W，竟然11s-卡過了= =

汗。。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int 
    maxn=2500000;
ll S[maxn],M[maxn];
int mu[maxn],phi[maxn],prime[maxn];
bool notprime[maxn];
map<int,ll>f;
void Pre(){
    notprime[1]=1,mu[1]=1,phi[1]=1;
    int pcnt=0;
    S[1]=1,M[1]=1;
    for (int i=2;i<maxn;i++){
        if (!notprime[i]){
            mu[i]=-1,phi[i]=i-1;
            prime[++pcnt]=i;
        }
        for (int j=1;j<=pcnt;j++){
            if (prime[j]*i>=maxn) break;
            notprime[prime[j]*i]=1;
            if (i%prime[j]){
                mu[i*prime[j]]=-mu[i];
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            } else{
                mu[i*prime[j]]=0;
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
        }
        S[i]=S[i-1]+(ll)phi[i],M[i]=M[i-1]+(ll)mu[i];
    }
}
ll solve_phi(int n){
    if (n<maxn) return S[n];
    if (f[n]) return f[n];
    ll ans=(ll)n*(1LL+n)/2LL,last;
    for (ll i=2;i<=n;i=last+1){
        last=n/(n/i);
        ans-=solve_phi(n/i)*(last-i+1);
    }
    f[n]=ans;
    return ans;
}
ll solve_mu(int n){
    if (n<maxn) return M[n];
    if (f[n]) return f[n];
    ll ans=1LL,last;
    for (ll i=2;i<=n;i=last+1){
        last=n/(n/i);
        ans-=solve_mu(n/i)*(last-i+1);
    }
    f[n]=ans;
    return ans;
}
int main(){
    Pre();
    int n,cas;scanf("%d",&cas);
    while (cas--){
        scanf("%d",&n);
        f.clear(),printf("%lld ",solve_phi(n));
        f.clear(),printf("%lld\n",solve_mu(n));
    }
    return 0;
}