emm标题全称应该叫“莫比乌斯反演求出可狄利克雷卷积的公式然后卷积之后搞杜教筛”
然后成功地困扰了我两天qwq
我们从最基本的题意开始，一步步往下推
首先题面给出的公式是$sumlimits_{i=1}^{n}sumlimits_{j=1}^{n}ijgcd(i,j)$
枚举gcd(i,j)=w，得到
$sumlimits_{w=1}^{n}wsumlimits_{i=1}^{n}sumlimits_{j=1}^{n}ij[w=gcd(i,j)]$
这时候我们设一个$f(x)=sumlimits_{i=1}^{n}sumlimits_{j=1}^{n}ij[x=gcd(i,j)]$
一个$F(x)=sumlimits_{i=1}^{n}sumlimits_{j=1}^{n}ij[x|gcd(i,j)]$
容易发现（其实就是为了凑莫比乌斯公式才搞的这两个函数，在构造函数之前就“容易发现”了）
$F(x)=sumlimits_{x|d}f(d)$
怎么样……像莫比乌斯反演公式吧
$f(d)=sumlimits_{d|x}mu(frac{x}{d})F(x)$
然后原式就变成了
$sumlimits_{w=1}^{n}wsumlimits_{w|t}mu(frac{t}{w})F(t)$
据说莫比乌斯反演构造的F(x)一定要简单易求
然后……自己找几组规律可以发现$F(x)=(x+2x+3x+......+frac{n}{x}x)^2$
然后……继续找规律发现一个问题，就是你可以把x提出来。qwq。
于是F(x)成功的变成了$x^2(1+2+3+......+frac{n}{x})^2$
然后我们回头去找扔掉的原式qwq
原式=$sumlimits_{w=1}^{n}wsumlimits_{w|t}mu(frac{t}{w})F(t)$
$=sumlimits_{w=1}^{n}w^3sumlimits_{w|t}mu(frac{t}{w})frac{t}{w}^2(1+.......+frac{n}{t})^2$
emm我们似乎发现了什么……
于是就设$d=frac{t}{w}$
然后把原式就整理成了
$sumlimits_{w=1}^{n}w^3sumlimits_{d=1}^{frac{n}{w}}mu(d)d^2(1+.......+frac{n}{wd})^2$
到此为止就有60分啦。不需要杜教筛狄利克雷卷积什么乱七八糟的玩意。
（然后剩下40分花掉了我一天+22个半小时）
然后我自己差不多就想到这里为止了。剩下的是rqy的脑补。
看到这里面一大堆下取整的玩意我们rqy非常不爽。
然后他先把公式颠倒了一下
$sumlimits_{d=1}^{n}mu(d)d^2sumlimits_{w=1}^{frac{n}{d}}w^3(1+......+frac{n}{wd})^2$
又令k=wd
然后改成枚举k
式子就变成了$sumlimits_{k=1}^{n}sumlimits_{d|k}mu(frac{k}{d})(frac{k}{d})^2d^3(1+....+frac{n}{k})^2$
=$sumlimits_{k=1}^{n}sumlimits_{d|k}mu(frac{k}{d})k^2d(1+....+frac{n}{k})^2$
发现有两项$k^2$,$(1+....+frac{n}{k})^2$跟d没什么卵关系
提出来提出来
$sumlimits_{k=1}^{n}k^2(1+....+frac{n}{k})^2sumlimits_{d|k}mu(frac{k}{d})d$
好，恭喜你$sumlimits_{d|k}mu(frac{k}{d})d=phi(k)$
为什么呢？因为根据狄利克雷卷积公式$mu*1=e$
$phi*1=n$
所以$n*mu=phi*1*mu=phi*e=phi$
然后你列一列这个卷积公式。
惊不惊喜？意不意外？
然后原式变成了$sumlimits_{k=1}^{n}k^2(1+....+frac{n}{k})^2phi(k)$
然后一看到$frac{n}{k}$有根号n种，非常激动，
然后现在的问题就变成了怎么快速求$k^2phi(k)$的前缀和
然后发现这个玩意用杜教筛好像很可做的样子
码了码了
#include<cstdio> #include<cstring> #include<cctype> #include<cstdlib> #include<algorithm> #include<map> #define maxn 4000100 using namespace std; map<long long,long long>_sum; long long sum[maxn]; long long phi[maxn]; long long prime[maxn],tot; bool vis[maxn]; long long mod; long long mod6; long long Pow(long long n,long long i,long long p){ long long ret=1; while(i){ if(i&1) ret=(ret*n)%p; n=(n*n)%p; i>>=1; } return ret; } inline long long calc(long long n,long long p){ n%=p; long long ans=((1+n)*n%p)*mod%p; ans=(ans*ans)%p; return ans; } inline long long calcs(long long n,long long p){ n%=p; long long ans=(n*(n+1)%p)*(2*n+1)%p; ans=ans*mod6%p; return ans; } long long calcsum(long long n,long long p){ if(n<maxn) return sum[n]; if(_sum.count(n)) return _sum[n]; long long x=2,ans=calc(n,p); while(x<=n){ long long y=n/(n/x); ans=((ans-((calcs(y,p)-calcs(x-1,p)+p)%p)*calcsum(n/x,p)%p)+p)%p; x=y+1; } return _sum[n]=ans; } int main(){ long long p,n; scanf("%lld%lld",&p,&n); mod=Pow(2,p-2,p); mod6=Pow(6,p-2,p); vis[1]=sum[1]=1; for(register long long i=2;i<maxn;++i){ if(!vis[i]){ prime[++tot]=i; phi[i]=i-1; sum[i]=((1LL*i*i)%p*phi[i])%p; } for(long long j=1;j<=tot&&i*prime[j]<maxn;++j){ vis[i*prime[j]]=1;long long now=i*prime[j]; if(i%prime[j]){ phi[now]=(phi[i]*(prime[j]-1))%p; sum[now]=(phi[now]*now)%p*now%p; } else{ phi[now]=(phi[i]*prime[j])%p; sum[now]=(phi[now]*now)%p*now%p; break; } } } for(long long i=2;i<maxn;++i) sum[i]=(sum[i]+sum[i-1])%p; long long x=1,ans=0; while(x<=n){ long long y=n/(n/x); ans+=((calcsum(y,p)-calcsum(x-1,p)+p)%p)*calc(n/x,p)%p; ans%=p; x=y+1; } printf("%lld",ans); return 0; }
然后这就是码qwq。