在cs中gcd的应用很广      一般可以求两个数的最大公约数

#include<iostream>
#include<cstdio>
using namespace std;
int gcd(int a,int b)
{
    if(a==0)
    return 0;
    else
    return (b==0)?a:gcd(b,a%b);
}
int main()
{
    int a,b;
    cin>>a>>b; 
    cout<<gcd(a,b)<<endl;
    return 0;
}

证明：

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

观察上述可知只需证明gcd(a,b)==gcd(b,a%b)

设a=qb+r      r=a-qb

设d 为a b 的公因子   d|a     d|b

可得d也为b  r的公因子  （根据同余满足 + - *）

得证

不过还有一个拓展gcd  以后在来补坑

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄