bzoj2956 模积和

2019-04-13 14:38发布

站内文章 / 模拟电子
15517 0 1122
class="markdown_views prism-atom-one-light">

Description

求∑i=1n∑j=1mnmodi∗mmodj" role="presentation">∑i=1n∑j=1mnmodi∗mmodj其中i!=j 对于100%的数据n,m<=10^9。

Solution

那个i!=j看着很不爽，直接容斥减掉下标相同的，然后拆开来就直接分块求和好了
刷水题都不能1a我真是太弱了

Code

#include #include #include #define rep(i,st,ed) for (int i=st;i<=ed;++i) typedef long long LL; const LL ny2=9970209; const LL ny6=3323403; const LL MOD=19940417; LL get1(LL x) { return x*(x+1)%MOD*ny2%MOD; } LL get2(LL x) { return x*(x+1)%MOD*(2*x%MOD+1)%MOD*ny6%MOD; } LL cal1(LL a,LL b) { return (get1(b)-get1(a-1)+MOD)%MOD; } LL cal2(LL a,LL b) { return (get2(b)-get2(a-1)+MOD)%MOD; } void solve(LL n,LL m) { LL a=n*n%MOD,b=m*m%MOD; for (LL i=1,j;i<=n;i=j+1) { j=n/(n/i); a=(a-(n/i)%MOD*cal1(i,j)%MOD+MOD)%MOD; } for (LL i=1,j;i<=m;i=j+1) { j=m/(m/i); b=(b-(m/i)%MOD*cal1(i,j)%MOD+MOD)%MOD; } LL ans=a*b%MOD; LL tot=n*m%MOD*n%MOD; LL tot1=0,tot2=0,tot3=0; for (LL i=1,j;i<=n;i=j+1) { j=n/(n/i); tot2=(tot2+(n/i)%MOD*cal1(i,j)%MOD)%MOD; } for (LL i=1,j;i<=n;i=j+1) { j=std:: min(m/(m/i),n); // printf("%lld %lld ", i,j); tot1=(tot1+(m/i)%MOD*cal1(i,j)%MOD)%MOD; } for (LL i=1,j;i<=n;i=j+1) { j=std:: min(n/(n/i),m/(m/i)); tot3=(tot3+(n/i)%MOD*(m/i)%MOD*cal2(i,j)%MOD)%MOD; } tot=((((tot-tot1*n%MOD)+MOD)%MOD-tot2*m%MOD+MOD)%MOD+tot3)%MOD; ans=(ans-tot+MOD)%MOD; if (ans<0) ans=(ans+MOD)%MOD; printf("%lld ", ans); } int main(void) { freopen("data.in","r",stdin); // freopen("myp.out","w",stdout); LL n,m; scanf("%lld%lld",&n,&m); if (mstd:: swap(n,m); solve(n,m); return 0; }

热门文章