BZOJ 2956 模积和 （分块加速）

2019-04-13 21:09发布

站内文章 / 模拟电子
14501 0 1689
∑i=1n∑1<=j<=m,j≠i(n mod i)∗(m mod j)=∑i=1n∑1<=j<=m,j≠i(n−i∗⌊ni⌋)∗(m−j∗⌊mj⌋)=∑i=1n(n−i∗⌊ni⌋)∗∑1<=j<=m,j≠i(m−j∗⌊mj⌋)=∑i=1n(n−i∗⌊ni⌋)∗∑j=1m(m−j∗⌊mj⌋)−∑i=1min(n,m)(n−i∗⌊ni⌋)∗(m−j∗⌊mj⌋)=(n2−∑i=1ni∗⌊ni⌋)∗(m2−∑i=1mi∗⌊mi⌋)−min(n,m)∗n∗m+(m∗∑i=1min(n,m)i∗⌊ni⌋+n∗∑i=1min(n,m)i∗⌊mi⌋)−∑i=1min(n,m)i2∗⌊ni⌋∗⌊mi⌋ 然后分块加速搞就可以了，总的复杂度：o(n√)，注意乘积越界的问题，还有取模的问题就搞定了。 #include #define LL long long #define FOR(i,x,y) for(int i = x;i < y;++ i) #define IFOR(i,x,y) for(int i = x;i > y;-- i) using namespace std; const int Mod = 19940417; LL inv; LL n,m; void Gcd(LL a,LL b,LL& d,LL& x,LL& y){ if(!b) {d = a;x = 1;y = 0;} else{Gcd(b,a%b,d,y,x);y -= x*(a/b);} } LL Inv(LL a,LL n){ LL d,x,y; Gcd(a,n,d,x,y);

热门文章