Peter_Matthew的博客

gcd和exgcd

2018-11-07

本文共182字，大约需要阅读1分钟。

gcd

STL库中有个template化的非递归版gcd，需要调用<alogorithm>
使用方式是

1
c=__gcd(a,b);

手写的话：

递归版：

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

非递归版：

1
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}

exgcd

递归版：

1
2
3
4
5
int exgcd(int a,int b,int &x,int &y)
{
    if(!b){x=1,y=0;return a;}
    int t=gcd(b,a%b,y,x);y-=a/b*x;return t;
}

非递归版：

1
2
3
4
5
6
7
8
9
10
11
int exgcd(int a,int b,int &x,int &y)
{
    int t=a%b,x0=1,y0=0,x1=0,y1=1;x=x1;y=y1;
    while(t)
    {
        x=x0-a/b*x1,y=y0-a/b*y1;
        x0=x1,y0=y1;x1=x,y1=y;
        a=b,b=t,t=a%b;
    }
    return a;
}
当前页共有次阅读，条评论。
标签: 数学
← 题解 T53818 【[退役欢乐赛Day2T3]谁是退役的人】 kmp →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏