【bzoj2956】模积和 数论分块

2019-04-14 15:22发布

站内文章 / 模拟电子
11556 0 1363

额，终于把图片搞出来了。 这个式子处理起来是O(n)的，但是我们发现n/i只用O(√n)个取值，我们枚举这O(√n)个取值。 假如枚举的取值为k，则把所有n/i=k的i求和即可 (k+1)*i>n>=k*i 所以i的取值区间为[n/(k+1)+1,n/k] 但是我们循环的时候枚举的是i，而不是k，每一次把i变成上一次的取值+1就可以了。 最后的那个式子也不难，就是一共有O(√n+√m)个取值，有用的区间只有O(√n)个，依次枚举即可。
#include #include #include #include #include #include #define mod 19940417 using namespace std; long long ans,n,m,ine; long long power(long long x,long long y) { long long ans=1; while (y) { if (y&1) ans=ans*x%mod; x=x*x%mod; y>>=1; } return ans; } long long sum(long long x) { return x*(x+1)/2%mod; } long long Sum(long long x) { return x*(x+1)%mod*(2*x+1)%mod*ine%mod; } long long cal(long long n) { long long ans=n*n%mod; long long last; for (long long i=1;i<=n;i=last+1) { last=n/(n/i); ans=(ans-(n/i)*(sum(last)-sum(i-1)+mod)%mod+mod)%mod; } return ans%mod; } int main() { scanf("%lld%lld",&n,&m); ine=3323403; if (n>m) swap(n,m); ans=cal(n)*cal(m)%mod; long long last; for (long long i=1;i<=n;i=last+1) { last=min(n/(n/i),m/(m/i));//n/i=k,last=n/k ans=(ans-n*m%mod*(last-i+1)%mod+m*(n/i)%mod*(sum(last)-sum(i-1)+mod)%mod+n*(m/i)%mod*(sum(last)-sum(i-1)+mod)%mod-(n/i)*(m/i)%mod*(Sum(last)-Sum(i-1)+mod)%mod+2*mod)%mod; } printf("%lld ",ans); return 0; }

热门文章