BZOJ 2956 模积和

2019-04-13 17:01发布

站内文章 / 模拟电子
15686 0 1355

Problem

BZOJ请戳我

Solution

∑i=1n∑j=1,i≠jm(nmodi)(mmodj)=∑i=1n(nmodi)∗∑j=1m(mmodj)−∑i=1min(n,m)(nmodi)(mmodi)=∑i=1n(nmodi)∗∑j=1m(mmodj)−∑I=1min(n,m)(n−⌊ni⌋i)(m−⌊mi⌋i)=∑i=1n(nmodi)∗∑j=1m(mmodj)−∑I=1min(n,m)(nm+⌊ni⌋⌊mi⌋i2−(m⌊ni⌋+n⌊mi⌋)i)" role="presentation">∑i=1n∑j=1,i≠jm(nmodi)(mmodj)=∑i=1n(nmodi)∗∑j=1m(mmodj)−∑i=1min(n,m)(nmodi)(mmodi)=∑i=1n(nmodi)∗∑j=1m(mmodj)−∑I=1min(n,m)(n−⌊ni⌋i)(m−⌊mi⌋i)=∑i=1n(nmodi)∗∑j=1m(mmodj)−∑I=1min(n,m)(nm+⌊ni⌋⌊mi⌋i2−(m⌊ni⌋+n⌊mi⌋)i)
前半部分同CQOI2007余数求和分块做一下，后半部分同样也是分块。然后∑i=1ni2=n∗(n+1)∗(2∗n+1)6" role="presentation">∑i=1ni2=n∗(n+1)∗(2∗n+1)6，6在模19940417意义下的逆元是3323403。

Code

#include #include using namespace std; typedef long long ll; const ll mod=19940417; ll n,m,ans,a,b,c; inline ll min(ll x,ll y){return xinline ll sum(ll l,ll r){return ((l+r)*(r-l+1)/2)%mod;} inline ll sqr(ll x){return x*(x+1)%mod*(x<<1|1)%mod*3323403%mod;} ll check(ll n) { ll res=n*n%mod; for(int i=1,j;i<=n;i=j+1) { j=n/(n/i); res=(res-(sum(i,j)*(n/i))+mod)%mod; } return res; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif scanf("%lld%lld",&n,&m); ans=(check(n)*check(m))%mod; if(n>m) swap(n,m); for(int i=1,j;i<=n;i=j+1) { j=min(n/(n/i),m/(m/i)); a=n*m%mod*(j-i+1)%mod; b=(m*(n/i)%mod+n*(m/i)%mod)%mod*sum(i,j)%mod; c=(n/i)*(m/i)%mod*((sqr(j)-sqr(i-1)+mod)%mod)%mod; ans=(ans-a+b-c+mod+mod)%mod; } printf("%lld ",ans); return 0; }