题意

  • 求gcd

证明

对于a和b的最大公因子d
a=pd，b=qd
则有c=(p-q)d，使得d为b和c的公因子

代码

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