[bzoj2956]模积和

2019-04-13 14:25发布

站内文章 / 模拟电子
11179 0 1036

题目大意

求∑ni=1∑mj=1,j!=i(nmodi)∗(mmodj)

思路

太麻烦了。
提供一个思路，nmodi=n−⌊ni⌋∗i
然后把原式中所有的都进行转化。
注意到有i!=j，先不理会它，然后最后减去。
学过莫比乌斯反演的都知道，对于任意i，⌊ni⌋只有根号n种取值。
然后本题就可做了。 #include #include #include #define fo(i,a,b) for(i=a;i<=b;i++) using namespace std; typedef long long ll; const ll mo=19940417; ll i,j,k,l,t,n,m,ans,x,y,z; ll getsum(ll x,ll y){ ll num=y*(y+1)%mo*(2*y+1)%mo*3323403%mo; ll t=(x-1)*x%mo*(2*x-1)%mo*3323403%mo; num=((num-t)%mo+mo)%mo; return num; } int main(){ scanf("%lld%lld",&n,&m); i=1; while (i<=n){ j=n/(n/i); x=(x+(j-i+1)*(i+j)/2%mo*(n/i)%mo)%mo; i=j+1; } i=1; while (i<=m){ j=m/(m/i); y=(y+(j-i+1)*(i+j)/2%mo*(m/i)%mo)%mo; i=j+1; } i=1; while (i<=min(n,m)){ j=min(n/(n/i),m/(m/i)); z=(z+getsum(i,j)*(n/i)%mo*(m/i)%mo)%mo; i=j+1; } ans=n*m%mo*n%mo*m%mo; ans=((ans-m*m%mo*x%mo)%mo+mo)%mo; ans=((ans-n*n%mo*y%mo)%mo+mo)%mo; ans=(ans+x*y%mo)%mo; i=1; x=0; while (i<=min(n,m)){ j=min(n/(n/i),min(n,m)); x=(x+(j-i+1)*(i+j)/2%mo*(n/i)%mo)%mo; i=j+1; } i=1; y=0; while (i<=min(n,m)){ j=min(m/(m/i),min(n,m)); y=(y+(j-i+1)*(i+j)/2%mo*(m/i)%mo)%mo; i=j+1; } ans=((ans-n*m%mo*min(n,m)%mo)%mo+mo)%mo; ans=((ans+m%mo*x%mo)%mo+mo)%mo; ans=((ans+n%mo*y%mo)%mo+mo)%mo; ans=((ans-z)%mo+mo)%mo; printf("%lld ",ans); }

热门文章