BZOJ2956:模积和 数学
思路:
其实是一道简单题.关键是要注意到题目中的一个条件:i≠j!!!
我们考虑用所有的情况减去i=j的情况.
所有的情况就很好求了.令f(n)=∑ni=1n%i,则所有的情况为f(n)∗f(m).
这玩意很容易分块求.
然后i=j的情况的贡献是:
(n%i)∗(m%i)=(n−i∗ni)∗(m−i∗mi)=nm+i2nimi−n∗imi−m∗ini
这样发现分开之后都可以分块求.
于是就O(√n)水过.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include<cstdio>#include<cstring>#include<cctype>#include<iostream>#include<algorithm>using namespace std; typedef long long LL; static const int mod=19940417,rev2=(mod+1)>>1,rev6=3323403; inline void mul(int&x,int y){x=(LL)x*y%mod;}inline void inc(int&x,int y){if((x+=y)>=mod)x-=mod;}inline void dec(int&x,int y){x=x<y?x+mod-y:x-y;}inline int calc(int n){//return sigma i^2 int res=n;mul(res,(LL)(n+1)*(2*n+1)%mod),mul(res,rev6);return res;}inline int cal(int l,int r){ int cl=calc(l-1),cr=calc(r); return cr<cl?cr+mod-cl:cr-cl;} inline int solve1(int n,int lim){//return sigma i*(n/i) int lst,t,res=0; for(int i=1;i<=lim;i=lst+1){ lst=min(lim,n/(n/i)); mul(t=n/i,(LL)(i+lst)*(lst-i+1)%mod),mul(t,rev2); inc(res,t); }return res;}inline int solve2(int n){//return sigma n%i return ((LL)n*n%mod+mod-solve1(n,n))%mod;}inline int solve3(int n,int m,int lim){//return sigma i^2(n/i)(m/i) int lst,t,res=0; for(int i=1;i<=lim;i=lst+1){ lst=min(n/(n/i),m/(m/i)),lst=min(lst,lim); mul(t=(LL)(n/i)*(m/i)%mod,cal(i,lst)); inc(res,t); }return res;} int main(){ int n,m;scanf("%d%d",&n,&m);register int i,j; int res=(LL)solve2(n)*solve2(m)%mod; dec(res,(LL)min(n,m)*n%mod*m%mod); inc(res,(LL)solve1(n,min(n,m))*m%mod); inc(res,(LL)solve1(m,min(n,m))*n%mod); dec(res,solve3(n,m,min(n,m))); printf("%d",res); return 0;} |
评论 (0)