这个构造真的太恐怖了。。。果然我还是太年轻。。。
这个问题终于让我把坑填完了。
它解决了我在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)); }
2022年8月25日 18:44
Meghalaya Board Model Paper 2023 Class 8 Pdf Download with Answers for Bengali Medium, English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Meghalaya Board 8th Class Model Paper Questions to Term1 & Term2 Exams at official website. New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.
2022年9月08日 19:59
In intermediate education, Botany is a very important subject for science group students for part-1 and part-2 first and the second year of junior and senior intermediate students, and the BIEAP has conducted the General Science examination tests including botany subject, download AP inter Botany Model Paper 2023 AP 1st Inter Botany Question Paper Pdf with solutions for all 1st and 2nd-year students for paper-1 and paper-2 exams 2023.