bzoj2956 模积和（数论分块）

2019-04-13 21:17发布

站内文章 / 模拟电子
11279 0 1487
用所有的减去i，j相同的，分三部分分块计算即可。
复杂度O(n+m)" role="presentation" style="position: relative;">O(n+m) #include using namespace std; #define ll long long #define inf 0x3f3f3f3f #define N 100010 #define mod 19940417 inline char gc(){ static char buf[1<<16],*S,*T; if(T==S){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;} return *S++; } inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f; } ll n,m,ans1,ans2,ans3,inv6; inline void inc(ll &x,int y){x+=y;x%=mod;} inline ll calc1(int i,int j){return (ll)(i+j)*(j-i+1)/2%mod;} inline ll calc2(ll x){return x*(x+1)%mod*(2*x+1)%mod*inv6%mod;} int main(){ // freopen("a.in","r",stdin); n=read();m=read();inv6=(mod+1)/6; if(n>m) swap(n,m); for(int i=1,j;i<=n;i=j+1){ j=n/(n/i);inc(ans1,calc1(i,j)*(n/i)%mod); }ans1=(ll)n*n-ans1;ans1%=mod; for(int i=1,j;i<=m;i=j+1){ j=m/(m/i);inc(ans2,calc1(i,j)*(m/i)%mod); }ans2=(ll)m*m-ans2;ans2%=mod; for(int i=1,j;i<=n;i=j+1){ j=min(n/(n/i),m/(m/i));ll res=n*m%mod*(j-i+1)%mod; inc(res,-(m*(n/i)+n*(m/i))%mod*calc1(i,j)%mod); inc(res,n/i*(m/i)%mod*(calc2(j)-calc2(i-1))%mod); inc(ans3,res); }ans1=ans1*ans2%mod-ans3;ans1%=mod;if(ans1<0) ans1+=mod; printf("%lld ",ans1); return 0; }

热门文章