莫比乌斯反演推柿子, 数论分块降复杂度, 最后时间复杂度为 O(n)
- #include<bits/stdc++.h>
- #define ll long long
- using namespace std;
- const int N=1e7+10,mod=20101009;
- int n,m,mi;
- ll p[N],tot;
- ll u[N];
- bool isp[N];
- void getu(int lim){
- u[1]=1;
- for(int i=2;i<=lim;i++){
- if(!isp[i]) u[i]=-1,p[++tot]=i;
- for(int j=1;j<=tot&&1LL*i*p[j]<=lim;j++){
- isp[p[j]*i]=1,u[i*p[j]]=-u[i];
- if(!(i%p[j])){u[i*p[j]]=0;break;}
- }
- }
- for(int i=2;i<=lim;i++) u[i]=((u[i]*i*i+u[i-1])%mod+mod)%mod;
- return;
- }
- ll solve(int d){
- ll x=n/d,y=m/d,l=1,r,lim=mi/d,res=0;
- while(l<=lim){
- r=min(x/(x/l),y/(y/l));
- ll temp=((x/l+1)*(x/l)/2%mod)*((y/l+1)*(y/l)/2%mod)%mod;
- res=((res+(u[r]-u[l-1])*temp)%mod+mod)%mod;
- l=r+1;
- }
- return res;
- }
- int main(){
- scanf("%d%d",&n,&m);
- mi=min(n,m);
- getu(mi);
- ll ans=0;
- int l=1,r;
- while(l<=mi){
- r=min(n/(n/l),m/(m/l));
- ans=(ans+solve(l)*(l+r)*(r-l+1)/2+mod)%mod;
- l=r+1;
- }
- printf("%lld",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2527744.html