类欧几里得算法

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

先考虑一个简单的问题

$$f(a,b,c,n)=\sum _{i=0}^n\lfloor \frac{ai+b}{c}\rfloor$$

我们这样来解决 $$\begin{array}{r}\\ & f(a,b,c,n)\\ & =\sum _{i=0}^n\lfloor \frac{ai+b}{c}\rfloor \\ & =f(a\mathrm{\%}c,b\mathrm{\%}c,c,n)+\sum _{i=0}^n(i\lfloor \frac{a}{c}\rfloor +\lfloor \frac{b}{c}\rfloor )\\ & =f(a\mathrm{\%}c,b\mathrm{\%}c,c,n)+\frac{n(n+1)}{2}\lfloor \frac{a}{c}\rfloor +(n+1)\lfloor \frac{b}{c}\rfloor \\ \\ & \mathrm{令}m=\lfloor \frac{an+b}{c}\rfloor \\ & \mathrm{则}f(a,b,c,n)\\ & =\sum _{i=0}^n\lfloor \frac{ai+b}{c}\rfloor \\ & =\sum _{i=0}^n\sum _{j=1}^m[\lfloor \frac{ai+b}{c}\rfloor \ge j]\\ & =\sum _{i=0}^n\sum _{j=0}^{m-1}[\lfloor \frac{ai+b}{c}\rfloor \ge j+1]\\ & =\sum _{i=0}^n\sum _{j=0}^{m-1}[ai+b\ge cj+c]\\ & =\sum _{i=0}^n\sum _{j=0}^{m-1}[ai>cj+c-b-1]\\ & =\sum _{i=0}^n\sum _{j=0}^{m-1}[i>\lfloor \frac{cj+c-b-1}{a}\rfloor ]\\ & =\sum _{j=0}^{m-1}n-\lfloor \frac{cj+c-b-1}{a}\rfloor \\ & =nm-f(c,c-b-1,a,m-1)\\ & \mathrm{可}\mathrm{以}\mathrm{开}\mathrm{始}\mathrm{递}\mathrm{归}，\mathrm{递}\mathrm{归}\mathrm{出}\mathrm{口}m=0\end{array}$$

然后我们考虑两个难一点的题目，同时解决这两个问题 $$\begin{array}{rl}& h(a,b,c,n)=\sum _{i=0}^n\lfloor \frac{ai+b}{c}{\rfloor }^{2}g(a,b,c,n)=\sum _{i=0}^{n}i\lfloor \frac{ai+b}{c}\rfloor \end{array}$$

先来看h $$\begin{array}{rl}& h(a,b,c,n)\\ =& \sum _{i=0}^n\lfloor \frac{ai+b}{c}{\rfloor }^2\\ =& \sum _{i=0}^n(\lfloor \frac{(a\mathrm{\%}c)i+(b\mathrm{\%}c)}{c}\rfloor +\lfloor \frac{a}{c}\rfloor i+\lfloor \frac{b}{c}\rfloor {)}^2\\ =& \sum _{i=0}^n(\lfloor \frac{(a\mathrm{\%}c)i+(b\mathrm{\%}c)}{c}{\rfloor }^2+\lfloor \frac{a}{c}{\rfloor }^2{i}^2+\lfloor \frac{b}{c}{\rfloor }^2+2\lfloor \frac{a}{c}\rfloor i\lfloor \frac{b}{c}\rfloor +2\lfloor \frac{(a\mathrm{\%}c)i+(b\mathrm{\%}c)}{c}\rfloor \lfloor \frac{a}{c}\rfloor i+2\lfloor \frac{(a\mathrm{\%}c)i+(b\mathrm{\%}c)}{c}\rfloor \lfloor \frac{b}{c}\rfloor \\ =& h(a\mathrm{\%}c,b\mathrm{\%}c,c,n)+2\lfloor \frac{a}{c}\rfloor g(a\mathrm{\%}c,b\mathrm{\%}c,c,n)+2\lfloor \frac{b}{c}\rfloor f(a\mathrm{\%}c,b\mathrm{\%}c,c,n)+\lfloor \frac{a}{c}{\rfloor }^2\frac{n(n+1)(2n+1)}{6}+2\lfloor \frac{a}{c}\rfloor \lfloor \frac{b}{c}\rfloor \frac{n(n+1)}{2}+(n+1)\lfloor \frac{b}{c}{\rfloor }^2\end{array}$$

这里我们只用关心第一项 $$\begin{array}{rl}& \mathrm{令}m=\lfloor \frac{an+b}{c}\rfloor \mathrm{则}\\ & h(a,b,c,n)\\ =& \sum _{i=0}^n\lfloor \frac{ai+b}{c}{\rfloor }^2\\ =& \sum _{i=0}^n(\sum _{j=1}^m[\lfloor \frac{ai+b}{c}\rfloor \ge j]{)}^2\\ =& \sum _{i=0}^n(\sum _{j=0}^{m-1}[i>\lfloor \frac{cj+c-b-1}{a}\rfloor ]{)}^2\\ =& \sum _{i=0}^n\sum _{j=0}^{m-1}[i>\lfloor \frac{cj+c-b-1}{a}\rfloor ]\sum _{k=0}^{m-1}[i>\lfloor \frac{ck+c-b-1}{a}\rfloor ]\\ =& \sum _{i=0}^n\sum _{j=0}^{m-1}\sum _{k=0}^{m-1}[i>\lfloor \frac{cj+c-b-1}{a}\rfloor ]\ast [i>\lfloor \frac{ck+c-b-1}{a}\rfloor ]\\ =& \sum _{i=0}^n\sum _{j=0}^{m-1}\sum _{k=0}^{m-1}[i>max(\lfloor \frac{cj+c-b-1}{a}\rfloor ,\lfloor \frac{ck+c-b-1}{a}\rfloor )]\\ =& \sum _{i=0}^n\sum _{j=0}^{m-1}\sum _{k=0}^{m-1}[i>max(\lfloor \frac{cj+c-b-1}{a}\rfloor ,\lfloor \frac{ck+c-b-1}{a}\rfloor )]\\ =& n{m}^2-\sum _{j=0}^{m-1}\sum _{k=0}^{m-1}max(\lfloor \frac{cj+c-b-1}{a}\rfloor ,\lfloor \frac{ck+c-b-1}{a}\rfloor )\\ =& n{m}^2-2\sum _{j=0}^{m-1}j\lfloor \frac{cj+c-b-1}{a}\rfloor -\sum _{j=0}^{m-1}\lfloor \frac{cj+c-b-1}{a}\rfloor \\ =& n{m}^2-2g(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)\end{array}$$ 推出来了。。。。。

然后我们来怼g $$\begin{array}{rl}& g(a,b,c,n)\\ =& \sum _{i=0}^{n}i\lfloor \frac{ai+b}{c}\rfloor \\ =& \sum _{i=0}^{n}i\lfloor \frac{(a\mathrm{\%}c)i+b\mathrm{\%}c}{c}+\lfloor \frac{a}{c}\rfloor i+\lfloor \frac{b}{c}\rfloor \rfloor \\ =& \sum _{i=0}^{n}i(\lfloor \frac{(a\mathrm{\%}c)i+b\mathrm{\%}c}{c}\rfloor +\lfloor \frac{a}{c}\rfloor i+\lfloor \frac{b}{c}\rfloor )\\ =& \sum _{i=0}^{n}i\lfloor \frac{(a\mathrm{\%}c)i+b\mathrm{\%}c}{c}\rfloor +\sum _{i=0}^n\lfloor \frac{a}{c}\rfloor i^2+\sum _{i=0}^n\lfloor \frac{b}{c}\rfloor i\\ =& \frac{n(n+1)(2n+1)}{6}\lfloor \frac{a}{c}\rfloor +\frac{n(n+1)}{2}\lfloor \frac{b}{c}\rfloor +\sum _{i=0}^{n}i\lfloor \frac{(a\mathrm{\%}c)i+b\mathrm{\%}c}{c}\rfloor \\ =& g(a\mathrm{\%}c,b\mathrm{\%}c,c,n)+\frac{n(n+1)(2n+1)}{6}\lfloor \frac{a}{c}\rfloor +\frac{n(n+1)}{2}\lfloor \frac{b}{c}\rfloor \end{array}$$ 同理我们只关心第一项 $$\begin{array}{rl}& g(a,b,c,n)\\ =& \sum _{i=0}^{n}i\lfloor \frac{ai+b}{c}\rfloor \\ =& \sum _{i=0}^n(i\sum _{j=1}^m[\lfloor \frac{ai+b}{c}\rfloor \ge j])\\ =& \sum _{i=0}^n(i\sum _{j=0}^{m-1}[i>\lfloor \frac{cj+c-b-1}{a}\rfloor ])\\ =& \sum _{i=0}^n\sum _{j=0}^{m-1}i[i>\lfloor \frac{cj+c-b-1}{a}\rfloor ]\\ =& \sum _{j=0}^{m-1}\sum _{i=\lfloor \frac{cj+c-b-1}{a}\rfloor +1}^{n}i\\ =& \sum _{j=0}^{m-1}\frac{(n+\lfloor \frac{cj+c-b-1}{a}\rfloor +1)\ast (n-(\lfloor \frac{cj+c-b-1}{a}\rfloor +1)+1)}{2}\\ =& \sum _{j=0}^{m-1}\frac{(n+\lfloor \frac{cj+c-b-1}{a}\rfloor +1)\ast (n-\lfloor \frac{cj+c-b-1}{a}\rfloor )}{2}\\ =& \sum _{j=0}^{m-1}\frac{n^2-\lfloor \frac{cj+c-b-1}{a}{\rfloor }^2+n-\lfloor \frac{cj+c-b-1}{a}\rfloor }{2}\\ =& \frac{n(n+1)m}{2}-\frac{\sum _{j=0}^{m-1}\lfloor \frac{cj+c-b-1}{a}{\rfloor }^2}{2}-\frac{\sum _{j=0}^{m-1}\lfloor \frac{cj+c-b-1}{a}\rfloor }{2}\\ =& \frac{n(n+1)m}{2}-\frac{h(c,c-b-1,a,m-1)}{2}-\frac{f(c,c-b-1,a,m-1)}{2}\end{array}$$ 推完了总结一下 $$\begin{array}{rl}& f(a,b,c,n)=\sum _{i=0}^n\lfloor \frac{ai+b}{c}\rfloor \\ & h(a,b,c,n)=\sum _{i=0}^n\lfloor \frac{ai+b}{c}{\rfloor }^2\\ & g(a,b,c,n)=\sum _{i=0}^{n}i\lfloor \frac{ai+b}{c}\rfloor \\ \\ & f(a,b,c,n)=f(a\mathrm{\%}c,b\mathrm{\%}c,c,n)+\frac{n(n+1)}{2}\lfloor \frac{a}{c}\rfloor +(n+1)\lfloor \frac{b}{c}\rfloor \\ & h(a,b,c,n)=h(a\mathrm{\%}c,b\mathrm{\%}c,c,n)+2\lfloor \frac{a}{c}\rfloor g(a\mathrm{\%}c,b\mathrm{\%}c,c,n)+2\lfloor \frac{b}{c}\rfloor f(a\mathrm{\%}c,b\mathrm{\%}c,c,n)+\lfloor \frac{a}{c}{\rfloor }^2\frac{n(n+1)(2n+1)}{6}+2\lfloor \frac{a}{c}\rfloor \lfloor \frac{b}{c}\rfloor \frac{n(n+1)}{2}+(n+1)\lfloor \frac{b}{c}{\rfloor }^2\\ & g(a,b,c,n)=g(a\mathrm{\%}c,b\mathrm{\%}c,c,n)+\frac{n(n+1)(2n+1)}{6}\lfloor \frac{a}{c}\rfloor +\frac{n(n+1)}{2}\lfloor \frac{b}{c}\rfloor \\ \\ & f(a,b,c,n)=nm-f(c,c-b-1,a,m-1)\\ & h(a,b,c,n)=n{m}^2-2g(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)\\ & g(a,b,c,n)=\frac{n(n+1)m}{2}-\frac{h(c,c-b-1,a,m-1)}{2}-\frac{f(c,c-b-1,a,m-1)}{2}\end{array}$$

void calfgh_baoli(ll a,ll b,ll c,ll n,ll&f,ll&g,ll&h){
    f=g=h=0;
    for(ll i=0;i<=n;i++) {
        f+=(a*i+b)/c;
        g+=i*((a*i+b)/c);
        h+=((a*i+b)/c)*((a*i+b)/c);
    }
}
// a>=0 b>=0 c>0 n>=0         -> O(lg(a,c))
void calfgh(ll a,ll b,ll c,ll n,ll&f,ll&g,ll&h){
    ll A=a/c,B=b/c,s0=n+1,s1=n*(n+1)/2,s2=n*(n+1)*(2*n+1)/6;
    f=s1*A+s0*B;
    g=s2*A+s1*B;
    h=s2*A*A+s0*B*B+2*s1*A*B-2*B*f-2*A*g;// 先减掉
    a%=c,b%=c;
    ll m=(a*n+b)/c;
    if(m!=0) {
        ll ff,gg,hh; calfgh(c,c-b-1,a,m-1,ff,gg,hh);
        f+=n*m-ff;
        g+=(n*m*(n+1)-hh-ff)/2;
        h+=n*m*m-2*gg-ff;
    }
    h+=2*B*f+2*A*g;//再加上
}