[BZOJ 2956]模积和 分块+数学

3/3/2017来源:C/C++教程人气:1090

一开始忘记了平方数列求和,郁闷: sum[n]=n*(n+1)*(2*n+1)/6 其实打一个表是看得出规律的,但是要进行运算我们还是得把他变成数学公式才可以啊: 对于取模运算:n%i=n−⌊ni⌋∗i 化简以后就是喜闻乐见地 分块了

#include<cstdio> #include<iostream> #include<cstring> #define inv 3323403ll #define Mod 19940417ll #define maxn 100021 #define LL long long using namespace std; LL n,m,s1,sm,s2,sn; LL Q(LL a,LL b){return (b-a+1)*(b+a)/2%Mod;} LL calc(LL x){return x*(x+1)%Mod*(2*x+1)%Mod*inv%Mod;} int main(){ scanf("%lld%lld",&n,&m); if(n>m)swap(n,m); for(LL num,i=1,j;i<=m;i=j+1){ j=m/(m/i);num=j-i+1; sm=(sm+num*m%Mod-Q(i,j)*(m/i)%Mod+Mod)%Mod; } for(LL num,i=1,j;i<=n;i=j+1){ j=n/(n/i);num=j-i+1; sn=(n*num%Mod-Q(i,j)*(n/i)%Mod%Mod+Mod)%Mod; s1=(s1+sn*sm%Mod)%Mod; } for(LL num,i=1,j;i<=n;i=j+1){ j=min(n/(n/i),m/(m/i));num=j-i+1; s2=(s2+n*m%Mod*num%Mod-m*(n/i)%Mod*Q(i,j)+Mod)%Mod; s2=(s2-n*(m/i)%Mod*Q(i,j)%Mod+(n/i)*(m/i)%Mod*(calc(j)-calc(i-1))%Mod+2*Mod)%Mod; } PRintf("%lld",(s1-s2+Mod)%Mod); return 0; }