题解 P3768 【简单的数学题】

很明显的把$gcd$提出来 $$\sum_{d=1}^nd\sum_{i=1}^n\sum_{j=1}^nij[gcd(i,j)==d]$$ 习惯性的提出来 $$\sum_{d=1}^nd^3\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}ij[gcd(i,j)==1]$$ 后面这玩意很明显的来一发莫比乌斯反演 $$\sum_{d=1}^nd^3\sum_{i=1}^{n/d}\mu(i)i^2(1+2+...[\frac{n}{id}])^2$$ 写起来好麻烦呀 我就设$sum(x)=1+2+3+...x$ 令$T=id$ 提出来！ $$\sum_{T=1}^nsum(\frac{n}{T})^2\sum_{d|T}d^3\frac{T}{d}^2\mu(\frac{T}{d})$$ 有些$d$可以约掉 $$\sum_{T=1}^nsum(\frac{n}{T})^2T^2\sum_{d|T}d\mu(\frac{T}{d})$$ 现在如果把后面给筛出来 可以$O(\sqrt n)$求啦 现在，问题来了 $$T^2\sum_{d|T}d\mu(\frac{T}{d})$$怎么算？？ 考虑一个式子： $$(id*\mu)(i)=\varphi(i)$$ 也就是说，$\mu$和$id(x)=x$的狄利克雷卷积等于$\varphi(i)$ ~~太神奇啦！！！~~ 所以说， $$T^2\sum_{d|T}d\mu(\frac{T}{d})=T^2\varphi(T)$$ 令$$f(i)=i^2\varphi(i)$$ $$S(n)=\sum_{i=1}^nf(i)$$ 杜教筛套路的式子拿出来 $$g(1)S(n)=\sum_{i=1}^n(g*f)(i)-\sum_{i=2}^ng(i)S(\frac{n}{i})$$ 还是发现有$\varphi(i)$的项 想到$$\sum_{d|i}\varphi(d)=i$$ 所以令$g(x)=x^2$ 所以 $$S(n)=\sum_{i=1}^n(g*f)(i)-\sum_{i=2}^ng(i)S(\frac{n}{i})$$ $$(g*f)(i)=\sum_{d|i}f(d)g(\frac{i}{d})=\sum_{d|i}d^2\varphi(d)\frac{i}{d}^2$$ $$=i^2\sum_{d|i}\varphi(d)=i^3$$ 所以 $$S(n)=\sum_{i=1}^ni^3-\sum_{i=2}^ni^2S(\frac{n}{i})$$ 根据小学奥数的经验： $1^3+2^3+....n^3=(1+2+....n)^2=sum(n)^2$ 所以现在有： $$ans=\sum_{T=1}^nsum(\frac{n}{T})^2\ T^2\sum_{d|T}d\mu(\frac{T}{d})$$ 前面可以数论分块 后面用杜教筛可以再非线性时间里面求出前缀和 这道题目就搞定啦 ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<set> #include<map> #include<vector> #include<queue> using namespace std; int MAX=8000000; #define MAXN 8000000 #define ll long long inline ll read() { ll x=0,t=1;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t; } ll MOD,n,inv6,inv2; int pri[MAXN],tot; ll phi[MAXN+10]; bool zs[MAXN+10]; map<ll,ll> M; ll fpow(ll a,ll b) { ll s=1; while(b){if(b&1)s=s*a%MOD;a=a*a%MOD;b>>=1;} return s; } void pre() { zs[1]=true;phi[1]=1; for(int i=2;i<=MAX;++i) { if(!zs[i])pri[++tot]=i,phi[i]=i-1; for(int j=1;j<=tot&&i*pri[j]<=MAX;++j) { zs[i*pri[j]]=true; if(i%pri[j])phi[i*pri[j]]=1ll*phi[i]*phi[pri[j]]%MOD; else{phi[i*pri[j]]=1ll*phi[i]*pri[j]%MOD;break;} } } for(int i=1;i<=MAX;++i)phi[i]=(phi[i-1]+1ll*phi[i]*i%MOD*i%MOD)%MOD; } ll Sum(ll x){x%=MOD;return x*(x+1)%MOD*inv2%MOD;} ll Sump(ll x){x%=MOD;return x*(x+1)%MOD*(x+x+1)%MOD*inv6%MOD;} ll SF(ll x) { if(x<=MAX)return phi[x]; if(M[x])return M[x]; ll ret=Sum(x);ret=ret*ret%MOD; for(ll i=2,j;i<=x;i=j+1) { j=x/(x/i); ll tt=(Sump(j)-Sump(i-1))%MOD; ret-=SF(x/i)*tt%MOD; ret%=MOD; } return M[x]=(ret+MOD)%MOD; } int main() { MOD=read();n=read(); MAX=min(1ll*MAX,n); inv2=fpow(2,MOD-2); inv6=fpow(6,MOD-2); pre(); ll ans=0; for(ll i=1,j;i<=n;i=j+1) { j=n/(n/i); ll tt=Sum(n/i);tt=tt*tt%MOD; ll gg=(SF(j)-SF(i-1))%MOD; ans+=gg*tt%MOD; ans%=MOD; } printf("%lld\n",(ans+MOD)%MOD); return 0; } ```