类欧几里得算法
- By Winniechen
一种用来快速求某些带有特殊性质的式子的和，一般复杂度为$O(\log n)$，有些特殊时刻，需要用到$\gcd$，因此为$O(\log^2 n)$
第一类
$f(a,b,c,n)=\sum\limits_{i=0}^n\lfloor\frac{a\times i+b}{c}\rfloor$
显然，若$a\ge c$，那么：
$$ f(a,b,c,n)=\sum\limits_{i=0}^n\lfloor\frac{(c\times k+t)\times i+b}{c}\rfloor \ =\sum\limits_{i=0}^nk\times i+\lfloor\frac{t\times i+b}{c}\rfloor \ =\frac{i\times (i+1)\times k}{2}+\sum\limits_{i=0}^n\lfloor\frac{t\times i+b}{c}\rfloor \ =\frac{i\times (i+1)\times k}{2}+f(t,b,c,n) $$同样，若$b\ge c$，那么：$f(a,b,c,n)=\sum\limits_{i=0}^n{\lfloor\frac{a\times i+c\times k+t}{c}\rfloor}=f(a,t,c,n)+k\times n$
因此，我们可以将上面两种情况转化为下面的这种：
$f(a,b,c,n),a< c,b<c$
$f(a,b,c,n)=\sum\limits_{i=0}^n\lfloor\frac{a\times i+b}{c}\rfloor=\sum\limits_{i=0}^n\sum\limits_{j=1}^m[\lfloor\frac{a\times i+b}{c}\rfloor\ge j],(m=\frac{a\times n+b}{c})$
$$ f(a,b,c,n) \ =\sum\limits_{i=0}^n\sum\limits_{j=0}^{m-1}{[a\times i > j\times c+c-b-1]} \ =\sum\limits_{i=0}^n\sum\limits_{j=0}^{m-1}[i> \frac{j\times c+c-b-1}{a}] \ = \sum\limits_{j=0}^{m-1}n-\lfloor\frac{c\times j-b+c-1}{a}\rfloor \ = n\times m-f(c,c-b-1,a,m-1) $$显然，对于项：$a,c$，经过了类似$\gcd$的$a=c,c=a%c$
因此，复杂度得以保证。
第二类
$g(a,b,c,n)=\sum\limits_{i=0}^ni\times \lfloor\frac{a\times i+b}{c}\rfloor$
类似前面的，推出$a,b\ge c$的情况。
$g(a,b,c,n)=\frac{n\times (n + 1)\times (2\times n+1)}{6} k_a+\frac{n\times (n+1)}{2}k_b+g(t_a,t_b,c,n)$
$g(a,b,c,n)=\sum\limits_{i=0}^ni\times \lfloor\frac{a\times i+b}{c}\rfloor=\sum\limits_{i=0}^ni\sum\limits_{j=1}^m[\lfloor\frac{a\times i+n}{c}\rfloor\ge j]$，$m$同上
发现后面的同上，所有我就跳过几步.jpg
$$ g(a,b,c,n)\ =\sum\limits_{i=0}^ni\sum\limits_{j=0}^{m-1}[i>\lfloor\frac{c\times j+c-b-1}{a}\rfloor ] \ =\sum\limits_{j=0}^{m-1} \frac{n\times (n+1)}{2}-\frac{x\times (x+1)}{2}(x=\lfloor\frac{c\times j+c-b-1}{a}\rfloor) \ =\frac{n\times (n+1)\times m+\sum\limits_{j=0}^{m-1}x+x^2}{2}\ = \frac{n\times (n+1)\times m-f(c,c-b-1,a,m-1)-h(c,c-b-1,a,m-1)}{2} $$$h(a,b,c,n)=\sum\limits_{i=0}^n \lfloor\frac{a\times i+b}{c}\rfloor ^2$，这个马上介绍...
但是显然，这个$g(a,b,c,d)$就只差$h(a,b,c,d)$了，其他都没有问题，都可以在$\log n$内解决
第三类
$h(a,b,c,n)=\sum\limits_{i=0}^n \lfloor\frac{a\times i+b}{c}\rfloor ^2$
同样类似上面的那个...
$$ h(a,b,c,n)=\ (a/c)^2n(n+1)(2n+1)/6+\ (b/c)^2(n+1)+(a/c)(b/c)n(n+1)+\ h(a%c,b%c,c,n)+2(a/c)g(a%c,b%c,c,n)+\ 2(b/c)f(a%c,b%c,c,n)$ $$ 其实也没啥，就是麻烦了点...就是需要稍微构造一下，因为正常推的话，显然是不能推的...
$n^2=2\times\frac{n\times (n+1)}{2}-n=2(\sum\limits_{i=0}^n i) -n$
$h(a,b,c,n)=\sum\limits_{i=0}^n2\sum\limits_{j=1}^xj-f(a,b,c,n)$
$h(a,b,c,n)=\sum\limits_{j=0}^{m-1}2\times (j+1)\sum\limits_{i=0}^n[\lfloor\frac{a\times i+b}{c}\rfloor \ge j+1]-f(a,b,c,n)$
$h(a,b,c,n)=2\sum\limits_{j=0}^{m-1}(j+1)\times(n- \lfloor\frac{c\times j+c-b-1}{a}])-f(a,b,c,n)$
$$ h(a,b,c,n)=\ n\times m\times (m+1) \ - 2\times g(c,c-b-1,a,m-1) \ - 2\times f(c,c-b-1,a,m-1) \ - f(a,b,c,n) $$ 完事了！第一种，难写难调跑得慢...（并且复杂度多了一个$\log$
#include#include #include #include #include #include #include #include #include
第二种，好写好调跑得快...
#include#include #include #include #include #include #include #include using namespace std;#define ll long long#define mod 998244353#define inv2 499122177#define inv6 166374059struct node{ ll f,g,h; node(){f=0,g=0,h=0;} node(ll a,ll b,ll c){f=a,g=b,h=c;} void print(){printf("%lld %lld %lld\n",f,h,g);}};node solve(ll n,ll a,ll b,ll c){ if(!a)return node((b/c)*(n+1)%mod,(n*(n+1)%mod*inv2)%mod*(b/c)%mod,(b/c)*(b/c)%mod*(n+1)%mod); node ret=node(); if(a>=c||b>=c) { ll t1=a/c,t2=b/c,s1=n*(n+1)%mod*inv2%mod,s2=n*(n+1)%mod*(2*n+1)%mod*inv6%mod; node tmp=solve(n,a%c,b%c,c); ret.f=(tmp.f+(n+1)*t2%mod+s1*t1%mod)%mod; ret.g=(tmp.g+s1*t2%mod+s2*t1%mod)%mod; ret.h=(t1*t1%mod*s2%mod+(n+1)*t2%mod*t2%mod+2*t1*t2%mod*s1%mod+2*t1*tmp.g%mod+2*t2*tmp.f%mod+tmp.h)%mod; return ret; } ll m=(a*n+b)/c;node tmp=solve(m-1,c,c-b-1,a); ret.f=(n*m%mod-tmp.f+mod)%mod; ret.g=((n*(n+1)%mod*m%mod-tmp.f-tmp.h)%mod+mod)*inv2%mod; ret.h=((n*m%mod*m%mod-tmp.g*2%mod-tmp.f)%mod+mod)%mod; return ret;}ll a,b,c,n;int main(){int T;scanf("%d",&T);while(T--)scanf("%lld%lld%lld%lld",&n,&a,&b,&c),solve(n,a,b,c).print();}