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

2019-11-06 08:24:09

字体：大中小

来源：转载

供稿：网友

一开始忘记了平方数列求和,郁闷: sum[n]=n*(n+1)*(2*n+1)/6 其实打一个表是看得出规律的,但是要进行运算我们还是得把他变成数学公式才可以啊: 对于取模运算:n%i=n−⌊ni⌋∗i $n/% i= {n-/lfloor {{n} /over {i}}/rfloor} *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;}

上一篇：存储单位bit、Byte，word关系

下一篇：AJAX学习