推得的式子:
∑t=1min(n,m)(∑k∣tk2μ(k)kt)(∑i=1⌊tn⌋)(∑i=1⌊tm⌋)
令f(n)=∑i=1ni=2n(n+1),ν(n)=n2μ(n)
那么原式化为∑t=1min(n,m)(ν∗Id)(t)f(⌊tn⌋)f(⌊tm⌋)
(ν∗Id)(t)是积性函数,就可以线性筛出来。 (ν∗Id)(pα)=ν(1)pα+ν(p)pα+1=pα−pα+1=(ν∗Id)(pα−1)⋅p
但只有三十分,请问大佬哪错了啊
代码
inline ll f(const ll i) {
return (i*(i+1)/2)%mod;
}
ll g[maxn];
void Init(const int &limit) {
static int prime[maxn],cnt;
static char not_prime[maxn];
g[1]=1;
for(R i(2);i<=limit;i++) {
if(~not_prime[i]) prime[cnt++]=i,g[i]=(ll)(i-i*i%mod+mod)%mod;
for(R j(0);j<cnt&&prime[j]<=limit/i;j++) {
not_prime[i*prime[j]]=0xff;
if(i%prime[j]==0) {
g[i*prime[j]]=(ll)(g[i]*prime[j]%mod+mod)%mod;
break;
}
g[i*prime[j]]=(g[i]*g[prime[j]]%mod+mod)%mod;
}
}
for(R i(1);i<=limit;i++) write(g[i]," \n"[i==limit]);
for(R i(1);i<=limit;i++) g[i]=(g[i]+g[i-1]+mod)%mod;
}
if(n>m) swap(n,m);
Init(m);
ll ans=0;
for(R i(1),j;i<=n;i=j+1) {
j=min(n/(n/i),m/(m/i));
(ans+=(ll)(g[j]-g[i-1]+mod)%mod*f(n/i)%mod*f(m/i)%mod+mod)%=mod;
}
write(ans,'\n');