2020 Wannafly Day3 D.求和(反演，杜教筛)

求和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod;
const int N=1e6+6;
bool vis[N];
ll prime[N],phi[N],tot;
ll cal_2(__int128 n){
    __int128 x=n*(n+1)*(n*2+1)/6;
    return x%mod;
}
ll cal_1(__int128 n){
    __int128 x=n*(n+1)/2;
    return x%mod;
}
void pre(){
    phi[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i])prime[++tot]=i,phi[i]=i-1;
        for(int j=1;j<=tot&&i*prime[j]<N;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    for(int i=1;i<N;i++)phi[i]=(phi[i]+phi[i-1])%mod;
}
map<int,ll>p;
ll s(ll n){
    if(n<N)return phi[n];
    if(p[n])return p[n];
    ll ans=cal_1(n);
    for(ll i=2,last;i<=n;i=last+1){
        last=n/(n/i);
        ll x=(last-i+1)%mod;
        ans-=s(n/i)*x%mod;
        ans=(ans%mod+mod)%mod;
    }
    return p[n]=ans;
}
int main(){
    ll n;
    scanf("%lld%lld",&n,&mod);
    pre();
    ll ans=0;
    for(ll i=1,last;i<=n;i=last+1){
        last=n/(n/i);
        ll x=(cal_2(last)-cal_2(i-1)+mod)%mod;
        ans+=s(n/i)*x%mod;
        if(ans>=mod)ans%=mod;
        if(ans<0)ans+=mod;
    }
    printf("%lld\n",ans);
}