BZOJ 2956 模积和 （分块）

2019-04-14 15:22发布

站内文章 / 模拟电子
16957 0 910
class="markdown_views prism-atelier-sulphurpool-light">

题目在这里呀！

题意

BZOJ 1257的加强版，多了一个？那就把它展开来啦。
∑i=1n∑j=1m(nmodi)∗(mmodj)(i!=j)
=∑i=1n∑j=1m(nmodi)∗(mmodj)−∑i=1n(n−⌊ni⌋∗i)∗(m−⌊mi⌋∗i)
=∑i=1n∑j=1m(nmodi)∗(mmodj)−∑i=1n(nm−n∗⌊mi⌋∗i−m∗⌊ni⌋∗i+⌊ni⌋∗⌊mi⌋∗i2) 用公式求出∑i 和 ∑i2 即可。
有模数那就把乘变成逆元吧（全都要变啊qwq）
本来大意了一下所以错了好多次emm
还以为是longlong的锅 //Suplex #include #include #include #include #include using namespace std; const int mod=19940417; const long long inv6=3323403; const long long inv2=9970209; long long n,m,next; long long ans,s1,s2,s3; long long calc(long long x) { long long res=x*x % mod; for(long long i=1;i<=x;i=next+1){ long long now=x/i; next=x/now; if(next>x) next=x; res=((res-(now*(i+next) % mod * (next-i+1) % mod * inv2 % mod)) % mod+mod) % mod; } return res; } inline long long sum(long long x) { return x*(x+1) % mod * (x+x+1) % mod * inv6 % mod; } int main() { scanf("%lld%lld",&n,&m); ans=calc(n)*calc(m) % mod; next=0; if(n>m) swap(n,m); for(long long i=1;i<=n;i=next+1){ next=min(n/(n/i),m/(m/i)); s1=(long long)n*m % mod * (next-i+1) % mod; s2=(long long)(n/i)*(m/i) % mod * (sum(next)-sum(i-1)+mod) % mod; s3=(long long)(n/i*m+m/i*n) % mod *(i+next) % mod * (next-i+1) % mod * inv2 % mod; ans=(ans-(s1+s2-s3) % mod + mod) % mod; } printf("%lld ",ans); return 0; }

热门文章