GCD EXGCD

Tang7O

发布于：2020年4月9日

字数统计: 79字 | 阅读时长: 1分

原理：a=b*q+r1; (a,b)==(b1,r1) ）( (a，b)为a，b的最小公约数） 代码如下：

int gcd(int a,int b)
{
    if(b==0)
        return a;
    gcd(b,a%b);
}

void exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){x=1;y=0;}
    else {exgcd(b,a%b,y,x);y-=(a/b)*x;}
}

本文作者： Tang7O

本文链接：https://tang7o.cn/2020/04/09/gcd/

博客内容遵循署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议。转载请注明出处！

更新于：2022年4月13日

算法

模板

会场安排问题（贪心算法）

题目如下Description假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不...

快速乘与快速幂

快速乘：(a*b)%c原理：将b转化为二进制的形式用b每一位的权重乘a再相加举个例子：$20 10=20(1010)_2=(202^31) + (202^20) + (202^11) + (...