题解 P3768 【简单的数学题】

· · 题解

这样反演好像更简单？就是处理gcd(i,j)的思路参照[NOI2010]能量采集，用φ卷积做

\sum ^{n}_{i=1}\sum ^{n}_{j=1}ij\gcd \left( i,j\right) =\sum ^{n}_{i=1}\sum ^{n}_{j=1}ij\sum _{k|i,k|j} φ(k) =\sum ^{n}_{k=1} φ(k) \sum _{k|i}\sum _{k|j}ij =\sum ^{n}_{k=1}\varphi \left( k\right) \cdot k^{2}\cdot (\sum ^{n/k}_{i=1}i)^{2} =\sum ^{n}_{k=1}\varphi \left( k\right) \cdot k^{2}\cdot \sum ^{n/k}_{i=1}i^{3} 
#include<bits/stdc++.h>
#define maxn 4600000
#define ll long long
using namespace std;

int pri[maxn],phi[maxn],pricnt=0;
ll sphi[maxn],p,n,inv;
bool notpri[maxn];
map<ll,ll> mp;
ll pw(ll a,ll b){
    ll ret=1;
    while(b){
        if(b&1)
            (ret*=a)%=p;
        (a*=a)%=p;
        b>>=1;
    }
    return ret;
}
void init(){
    inv=pw(6,p-2);
    phi[1]=1;
    for(int i=2;i<maxn;i++){
        if(!notpri[i]){
            pri[++pricnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=pricnt;j++){
            if(i*pri[j]>=maxn)
                break;
            notpri[i*pri[j]]=true;
            if(i%pri[j]==0){
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
    for(int i=1;i<maxn;i++)
        sphi[i]=(sphi[i-1]+1LL*i*i%p*phi[i]%p)%p;
}
ll s2(ll x){
    x%=p;
    return x*(x+1)%p*(2*x+1)%p*inv%p;
} 
ll s3(ll x){
    x%=p;
    return (x*(x+1)/2)%p*((x*(x+1)/2)%p)%p;
}
ll calc(ll x){
    if(x<maxn)
        return sphi[x];
    if(mp[x])
        return mp[x];
    ll pos,ret=s3(x);
    for(ll i=2;i<=x;i=pos+1){
        pos=x/(x/i);
        (ret-=1LL*(s2(pos)-s2(i-1)+p)%p*calc(x/i)%p)%=p;
    }
    (ret+=p)%=p;
    return mp[x]=ret;
}
ll solve(){
    ll pos,ret=0;
    for(ll i=1;i<=n;i=pos+1){
        pos=n/(n/i);
        (ret+=1LL*(calc(pos)-calc(i-1)+p)%p*s3(n/i)%p)%=p;
    }
    (ret+=p)%=p;
    return ret;
}
int main(){
    scanf("%lld%lld",&p,&n);
    init();
    printf("%lld\n",solve());
    return 0;
}