欧几里德算法专题

摘要

鉴于初等数论的内容太多,于是单独分出一个欧几里德算法的文章,主要讲欧几里德算法,扩欧和类欧

欧几里得算法

即辗转相除法,基于 的原理,用于求解最大公约数的问题

int gcd(int a,int b){return b?gcd(b,a%b):a;}

LG4549 裴蜀定理

给出 n 个数 ,求一组整数序列 使得 的值为正且最小,输出这个和。

实际上和裴蜀定理没什么关系,直接全部 GCD 即可

#include<cstdio>
using namespace std;
int n,g=0,a;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        g=gcd(a>0?a:-a,g);
    }
    printf("%d",g);
    return 0;
}

扩展欧几里德算法

扩展欧几里得算法是欧几里得算法的推广。利用欧几里得算法的思想和递归求得不定方程

的一组 x 和 y 的特解。也可求解

的一组特解(裴蜀定理)

int exgcd(int a,int b,int & x,int & y){
    if(b==0)return x=1,y=0,a;
    int t=exgcd(b,a%b,y,x);
    return y=y-x*(a/b),t;
}

算法过程

扩欧实际上就是类似辗转相除法的递归。我们知道

假设现在我们已经求得 的一组特解,现在我们用 来推出 .

显然, ,因此

于是对应项系数为 0, 可以得出

于是递归求解即可

LG1516 青蛙的约会

给定 x,y,m,n,l, 求最小的正整数t,使

由等式:

如果 ,则 exgcd 求解方程,否则方程无整数解。

,得到 . 令 ,则

, 不定方程有整数解;否则无整数解(Impossible)。

若原方程有解整数解,则令

所以 与原方程同解。又因为 ,所以可用扩欧求解 ,进而求解 , 再取最小整数解即可。

#include<bits/stdc++.h>
#define lld long long
using namespace std;
lld x,y,m,n,l;
lld exgcd(lld a,lld b,lld & x,lld & y){
    if(b==0)return x=1,y=0,a;
    lld t=exgcd(b,a%b,y,x);
    return y=y-(a/b)*x,t;
}
int main(){
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
    lld p=n-m,q=x-y,k,t;
    lld g=exgcd(p,l,t,k);
    if(q%g)puts("Impossible");
    else {
        lld r=l/g;
        printf("%lld",(q/g*t%r+r)%r);
    }
    return 0;
}

类欧几里得算法

类欧几里德算法由洪华敦在 2016 年冬令营营员交流中提出的内容,其本质可以理解为,使用一个类似辗转相除法来做函数求和的过程。我们用几个~喵~不可言的问题引入这个算法。

问题一

我们考虑一个可爱的求和式子:

其中 是常数。这个式子和我们以前见过的式子都长得不太一样。带向下取整的式子容易让人想到数论分块,然而数论分块似乎不适用于这个求和。但是我们是可以做一些预处理的。

如果说 或者 ,意味着可以将 取模以简化问题:

那么问题转化为了 的情况。观察式子,你发现只有 这一个变量。因此要推就只能从 下手。在推求和式子中有一个常见的技巧,就是条件与贡献的放缩与转化。具体地说,在原式 中, 是条件,而 是对总和的贡献。

要加快一个和式的计算过程,所有的方法都可以归约为贡献合并计算。但你发现这个式子的贡献难以合并,怎么办?将贡献与条件做转化得到另一个形式的和式。具体地说,我们直接把原式的贡献变成条件:

现在多了一个变量 ,既然算 的贡献不方便,我们就想办法算 的贡献。因此想办法搞一个和 有关的贡献式。这里有另一个家喻户晓的变换方法,笔者概括为限制转移。具体来说,在上面的和式中 限制 的上界,而 限制 的上界。为了搞 ,就先把 j 放到贡献的式子里,于是我们神仙地交换一下 的求和算子,强制用 限制 的上界。

这样做的目的是让 摆脱 的限制,现在 都被 限制,而贡献式看上去是一个条件,但是我们仍把它叫作贡献式,再对贡献式做变换后就可以改变 的限制关系。于是我们做一些放缩的处理。首先把向下取整的符号拿掉

然后可以做一些变换

最后一步,向下取整得到:

你发现你把 拿出来,把 丢进去了。于是就可以把变量 消掉了!具体地,令 ,那么原式化为

这是一个递归的式子。并且你发现 分子分母换了位置,又可以重复上述过程。先取模,再递归。这就是一个辗转相除的过程,这也是类欧几里德算法的得名。

问题二

理解了最基础的类欧几里德算法,我们再来思考以下两个变种求和式:

推导 g

我们先考虑 ,类似地,首先取模:

接下来考虑 的情况,令 。之后的过程我会写得很简略,因为方法和上文略同:

这时我们设 ,可以得到

推导 h

同样的,首先取模:

考虑 的情况, .

这样用到一个技巧。我们先把 拆一下: . 这样在添加变量 的时侯就只会变成一个求和算子,不会出现 的情况:

接下来化一下和式

因此原式即为

模板与实现

在计算的时侯,因为 3 个函数各有交错递归,因此可以考虑三个一起整体递归来求,否则有很多项会被多次计算。或者采用记忆化。

模板:Luogu5170

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int P= 998244353;
int i2= 499122177,i6= 166374059;
struct data{data(){f=g=h=0;}
    int f,g,h;
};// 三个函数打包
data calc(int n,int a,int b,int c) {
    int ac=a/c,bc=b/c,m=(a*n+b)/c,n1=n+1,n21=n*2+1;
    data d;
    if(a==0){// 迭代到最底层
        d.f=bc*n1%P;
        d.g=bc*n%P*n1%P*i2%P;
        d.h=bc*bc%P*n1%P;
        return d;
    }
    if(a>=c||b>=c){// 取模
        d.f=n*n1%P*i2%P*ac%P+bc*n1%P;
        d.g=ac*n%P*n1%P*n21%P*i6%P+bc*n%P*n1%P*i2%P;
        d.h=ac*ac%P*n%P*n1%P*n21%P*i6%P+bc*bc%P*n1%P+ac*bc%P*n%P*n1%P;
        d.f%=P,d.g%=P,d.h%=P;

        data e=calc(n,a%c,b%c,c);// 迭代

        d.h+=e.h+2*bc%P*e.f%P+2*ac%P*e.g%P;
        d.g+=e.g,d.f+=e.f;
        d.f%=P,d.g%=P,d.h%=P;
        return d;
    }
    data e=calc(m-1,c,c-b-1,a);
    d.f=n*m%P-e.f,d.f=(d.f%P+P)%P;
    d.g=m*n%P*n1%P-e.h-e.f,d.g=(d.g*i2%P+P)%P;
    d.h=n*m%P*(m+1)%P-2*e.g-2*e.f-d.f;d.h=(d.h%P+P)%P;
    return d;
}
int T, n, a, b, c;
signed main() {
    scanf("%lld", &T);
    while(T--) {
        scanf("%lld%lld%lld%lld", &n, &a, &b, &c);
        data ans=calc(n,a,b,c);
        printf("%lld %lld %lld\n",ans.f,ans.h,ans.g);
    }
    return 0;
}

  转载请注明: Sshwy's Blog 欧几里德算法专题

 上一篇
网络流入门之费用流 网络流入门之费用流
摘要 之前写的《网络流初步》内容太多,因此单独分一个费用流出来。本文的内容可能涉及到《网络流入门之最大流》的内容,建议先食用后者。 2019.6.15 编入精选文章 费用流给定一个网络 ,每条边除了有容量限制 $c(u,
2019.05.03
下一篇 
SCOI2010 幸运数字 SCOI2010 幸运数字
摘要 幸运数字:只包含数字 6 和 8 的那些号码。近似幸运数字:幸运数字的倍数。求 的近似幸运数字的个数。 . 首先想到的就是容斥,考虑预处理所有的近似幸运数字,直接容斥是自
2019.05.01
  目录