这个构造真的太恐怖了。。。果然我还是太年轻。。。
这个问题终于让我把坑填完了。
它解决了我在1222的推导上的主要问题
$\sum_{i=1}^{n}\sum_{j=1}^{n/i}n/i/j*e(gcd(i,j))$
$\sum_{i=1}^{n}n/i*2^{\omega(i)}$
$\omega(i)$表示i的不同质因子个数。
然后发现没法做了,后面的不会算。
这个问题里面提到了$2^{\omega(i)}=\sum_{d|i}(\mu(d))^2$
我这个ZZ觉得真的妙。
然后就可以做了,因为$\sum_{i=1}^{n}(\mu(d))^2=\sum_{i=1}^{\sqrt{n}}n/i^2*\mu(i)$
然后就被卡常了
#include<cstdio> #include<cmath> #define size 7000000 #define eps 1e-11 #define size2 15000 #define inf 100000000000000ll using namespace std; long long l,r,n; int cnt; int mu[size+5],mu2[size+5],d[size+5],last[size+5],prime[500005]; long long smu[size2],smu2[size2],sd[size2]; bool vis[size+5]; inline long long min(long long x,long long y){return x<y?x:y;} void pre(){ mu[1]=1;d[1]=1; for(int i=2;i<=size;i++){ if(!vis[i])prime[++cnt]=i,mu[i]=-1,d[i]=2,last[i]=1; for(int j=1;(j<=cnt)&&(prime[j]*i<=size);j++){ int k=prime[j]*i; vis[k]=true; if(i%prime[j]==0){mu[k]=0;last[k]=last[i];d[k]=d[i]+d[last[i]];break;} else mu[k]=-mu[i],d[k]=d[i]<<1,last[k]=i; } } for(int i=1;i<=size;i++)mu2[i]=mu[i]*mu[i]+mu2[i-1],mu[i]+=mu[i-1],d[i]+=d[i-1]; } inline long long Smu2(long long k){return k<=size?mu2[k]:smu2[n/k];} inline long long Smu(long long k){return k<=size?mu[k]:smu[n/k];} inline long long Sd(long long k){return k<=size?d[k]:sd[n/k];} inline long long solve(long long p){ n=p; for(int i=n/size;i;i--){ long long t=n/i; smu2[i]=0; int tmp=int(sqrt(t)+eps); for(int j=1;j<=tmp;j++)smu2[i]+=t/j/j*(mu[j]-mu[j-1]); smu[i]=1; for(int j=1;j<=tmp;j++){ smu[i]-=(t/j-t/(j+1))*mu[j]; if((t/j!=j)&&(j!=1))smu[i]-=Smu(t/j); } sd[i]=0; for(int j=1;j<=tmp;j++){ sd[i]+=t/j; if(t/j!=j)sd[i]+=j*(t/j-t/(j+1)); } } int tmp=int(sqrt(p)+eps);long long ans=0; for(int i=1;i<tmp;i++)ans+=(mu2[i]-mu2[i-1])*Sd(p/i)+(Smu2(p/i)-Smu2(p/(i+1)))*d[i]; if(p/tmp==tmp)ans+=(mu2[tmp]-mu2[tmp-1])*d[tmp]; else ans+=(mu2[tmp]-mu2[tmp-1])*d[p/tmp]+(mu2[p/tmp]-mu2[p/(tmp+1)])*d[tmp]; return (ans+p)>>1; } int main(){ pre(); scanf("%lld%lld",&l,&r);l--; printf("%lld",solve(r)-solve(l)); }