#include<stdio.h> int gcd (int a,int b) { a=(a<0)?-a:a; b=(b<0)?-b:b;//确保为正数 if (a==b) { return a; } else if (a>b) { return gcd (a-b,b); } else { return gcd (b-a,a);//递归计算 } } int main() { int a,b; scanf("%d %d",&a,&b); printf("%d",gcd(a,b)); return 0; }
更相减损法的原理是:两个数的最大公约数等于它们中较大的数减去较小的数的差与较小的数的最大公约数。
这道题还可以用辗转相除法来计算。