类欧几里得算法总结

雅礼集训某天的东西。。

定义

首先写下定义，其实就是几个式子。

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

$$g(a,b,c,n)=\sum_{i=0}^ni\lfloor {ai+b \over c} \rfloor$$

$$h(a,b,c,n)=\sum_{i=0}^n\lfloor {ai+b \over c} \rfloor^2$$

类欧几里得就是如何快速求这几个式子。下面先推第一个，第二个要用到第一个，第三个要用到第二个。

为了方便(懒)，下面下取整都不写了，而且$m={an+b \over c}$

f

当$c \leq a$或者$c \leq b$的时候，这样就可以把后面的式子拆开，整除的算一部分，余数算一部分。也就是

$$f(a,b,c,n)={a\over c}\times n \times {n+1 \over 2} +{b \over c} \times (n+1)+f(a \%c,b\%c,c,n)$$

那$a$和$b$都小于$c$怎么办呢？

我们可以从几何的角度来理解这个式子，可以发现$\sum$里面的式子很像一个直线的解析式。意义其实是一条倾斜直线与$x=0$和$x=n$两条铅垂线组成的直角梯形内整点数量（不包括纵坐标为0的点，包括在线上的点）。

这个式子就是在枚举一条纵线，统计上面的整点。现在我们可以枚举一个横线，再统计上面的点的个数。

$$f(a,b,c,n)=\sum_{i=0}^n\sum_{j=0}^{m-1}[{ai+b \over c} \geq j+1]$$

这样的话看上去效率好像更低了。但是这个式子能化啊= =

先把$c$乘过去，再把$b$移过去

$$=\sum_{i=0}^n\sum_{j=0}^{m-1}[ai \geq cj+c-b]$$

减上$1$把大于等于化成等于，把$a$除过去

$$=\sum_{i=0}^n\sum_{j=0}^{m-1}[i>{cj+c-b-1 \over a}]$$

这样就可以不枚举第一层了，直接化成$n$。(次数是一样的)

$$=\sum_{j=0}^{m}(n-{cj+c-b-1 \over a})$$

把这个$\sum$拆开

$$=m\times n-\sum_{j=0}^{m}{cj+c-b-1 \over a}$$

这样就能看出来了吧，这就是$f$！

$$f(a,b,c,n)=m\times n-f(c,c-b-1,a,m-1)$$

发现又可以递归了，其实把$m$带入一下：

$$f(a,b,c,n)={an+b \over c}\times n-f(c,c-b-1,a,{an+b \over c}-1)$$

这样每次由$(a,c)$变成$(c,a\%c)$，因此复杂度与欧几里得算法一致，也就是$O(\log n)$

g

当$c \leq a$或者$c \leq b$的时候，和上面一样，就是需要用一下平方和公式。

$$g(a,b,c,n)={a\over c}\times n \times (n+1)\times {2n+1 \over 6}+{b\over c}\times n\times {n+1\over 2}+g(a\%c,b\%c,c,n)$$

$a$和$b$都小于$c$和上面一样推

$$g(a,b,c,n)=\sum_{i=0}^ni\sum_{j=0}^{m-1}[{ai+b \over c} \geq j+1]$$

$$=\sum_{i=0}^ni\sum_{j=0}^{m-1}[i>{cj+c-b-1 \over a}]$$

这里因为多了一位，所以要套一下求和公式

$$={1\over2}\sum_{j=0}^{m-1}(n+1+{cj+c-b-1 \over a})\times(n-{cj+c-b-1 \over a})$$

把它乘开

$$={1\over2}\sum_{j=0}^{m-1}n\times (n+1)-{cj+c-b-1 \over a}+({cj+c-b-1 \over a})^2$$

发现前面的是$f$，后面的是$g$

$$g(a,b,c,n)={1 \over 2}[(n+1)\times n\times m-f(c,c-b-1,a,m-1)-g(c,c-b-1,a,m-1) ]$$

h

当$c \leq a$或者$c \leq b$的时候，也很麻烦。。

$$h(a,b,c,n)=({a\over c})^2\times {n(n+1)(2n+1)\over 6}+({b\over c})^2\times(n+1)+{a\over c}\times{b\over c}\times n(n+1)+h(a\%c,b\%c,c,n)+2\times {a\over c}\times g(a\%c,b\%c,c,n)+2\times {b\over c}\times f(a\%c,b\%c,c,n)$$

推剩下的情况就和上面的不一样了。

我们先试着构造一个$n^2$

$$n^2=2\times \frac{n(n+1)}{2}-n=2\sum_{i=0}^ni-n$$

那么我们就把$({ai+b\over c})^2$拆开

$$h(a,b,c,n)=\sum_{i=0}^n(2\times \sum_{j=1}^{(ai+b)/c}j-{ai+b\over c})$$

这样拆出一个$f$，再交换一下主体

$$=2\times \sum_{j=0}^{m-1}(j+1)\times\sum_{i=0}^n[{ai+b \over c} \geq j+1]-f(a,b,c,n)$$

和前面一样的化

$$h(a,b,c,n)=2\times \sum_{j=0}^{m-1}(j+1)*(n-{cj+c-b-1 \over a})-f(a,b,c,n)$$

那最后就成了

$$h(a,b,c,n)=nm(m+1)-2g(c,c-b-1,a,m-1)-2f(c,c-b-1,a,m-1)-f(a,b,c,n)$$

例题 bzoj 3817

题意

给定$n\leq 10^9,r\leq10^4$求

$$\large \sum_{d=1}^{n} (-1)^{\lfloor \sqrt{d\times r\times d} \rfloor}$$

题解

设$x=\sqrt r$，则

$$
\begin{align}
-1^{dx } & =1-2( dx \% 2) \\
&=1-2(dx – \frac{dx}{2} * 2) \\
&= 1+4\frac{dx}{2} + 2 dx
\end{align}
$$

那么

$$原式 =n + 4 \sum_{d=1}^{n} \frac{dx}{2}-2\sum_{d=1}^{n}dx$$

这样就是类欧的式子了。

代码

#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;
double t;
ll m,n;
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
ll calc(ll n,ll a,ll b,ll c)
{
    if (!n) return 0ll;
    ll g=gcd(a,gcd(b,c));
    a/=g,b/=g,c/=g;
    ll k=(t*b+c)/a,ans=n*(n+1)/2*k;
    c-=k*a,k=(t*b+c)/a*n;
    ans+=n*k,ans-=calc(k,b*b*m-c*c,a*b,-a*c);
    return ans;
}
main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&m),t=sqrt(m);
        if ((ll)t==t)
            printf("%lld\n",(ll)(m&1)?((n&1)?-1:0):n);
        else
            printf("%lld\n",n+(calc(n,2,1,0)<<2)-(calc(n,1,1,0)<<1));
    }

 }