P3768 简单的数学题

· · 个人记录

莫反的做法不太会（有空来补）

\text{Solution}

\sum_{i=1}^{n}\sum_{j=1}^{n}ij(i,j)

因为

\sum_{d|n} \phi(d)=n \sum_{i=1}^{n}\sum_{j=1}^{n}ij\sum_{d|(i,j)}\phi(d) \sum_{i=1}^{n}\sum_{j=1}^{n}ij\sum_{d|i,d|j}\phi(d)

考虑枚举 d ,d\in[1,n]，且 i,j 为 d 的倍数

\sum_{d=1}^{n}\phi(d)\sum_{d|i}i\sum_{d|j}j \sum_{d=1}^{n}\phi(d)d^2(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}i)^2

观察到有 \frac{n}{d}，整个式子可以整除分块。

解决下

\sum_{d=1}^{n}\phi(d)d^2

记

S(x)=\sum_{i=1}^{n}\phi(i)i^2 f(x)=\phi(x)x^2 g(x)=x^2

f,g均为积性函数。

(f*g)(x)=\sum_{d|x}f(d)g(\frac{x}{d})=\sum_{d|x}\phi(d)d^2\dfrac{x^2}{d^2}=x^2\sum_{d|x}\phi(d)=x^3

然后杜教筛

S(x)=\dfrac{\sum_{i=1}^{n}(f*g)(i)-\sum_{i=2}^{n}g(i)*S(\frac{x}{i})}{g(0)}

\text{Code}

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>

#define N (int)(5e6+5)
#define ll long long

using namespace std;
int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}
ll lrd() {
    ll f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}

bool vis[N];
ll phi[N],mod,n,inv6;
int pri[N>>2],tot;
map<ll,ll>ans_phi;

ll fpow(ll x,ll y) {
    ll res=1;
    while(y) {
        if(y&1) res=res*x%mod;
        x=x*x%mod; y>>=1;
    }
    return res;
}

void init() {
    phi[1]=1;
    for(int i=2;i<N;i++) {
        if(!vis[i]) pri[++tot]=i,phi[i]=i-1;
        for(int j=1;j<=tot&&pri[j]*i<N;j++) {
            vis[i*pri[j]]=1;
            if(i%pri[j]==0) {
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            phi[i*pri[j]]=phi[i]*phi[pri[j]];
        }
    }
    for(int i=1;i<N;i++) phi[i]=(phi[i]*i%mod*i%mod+phi[i-1])%mod;
}

ll SUM1(ll x) {
    x%=mod;
    return (x*(x+1ll)/2ll)%mod;
}

ll SUM2(ll x) {
    x%=mod;
    return x*(x+1)%mod*(2*x+1)%mod*inv6%mod;
}

ll SUM3(ll x) {
    return SUM1(x)*SUM1(x)%mod;
}

ll get_phi(ll x) {
    if(x<N) return phi[x];
    if(ans_phi[x]) return ans_phi[x];
    ll ans=SUM3(x);
    for(ll l=2,r;l<=x;l=r+1) {
        r=x/(x/l);
        ans-=(SUM2(r)-SUM2(l-1)+mod)%mod*get_phi(x/l)%mod;
        ans%=mod;
    }
    return ans_phi[x]=ans;
}

void solve() {
    init(); inv6=fpow(6,mod-2);
    ll ans=0;
    for(ll l=1,r;l<=n;l=r+1) {
        r=n/(n/l);
        ans=(ans+SUM3(n/l)*(get_phi(r)-get_phi(l-1))%mod)%mod;
    }
    ans=(ans%mod+mod)%mod;
    printf("%lld",ans);
}

int main() {
    mod=lrd(); n=lrd();
    solve();
    return 0;
}