GCD最大公约数
程序员文章站
2024-03-20 12:03:40
...
-GCD
已知两个正整数a,b求最大公约数。
- (a,b)可以写成a=b* q1+r1的形式(q1,r1都是实数)(a,b)的GCD即为(b,r1)的GCD
所以b=r1* q2+r2;
r1=r2* q3+r3;
……
rn=rn+1* qn+2;
所以最大公约数为qn+2。
证明:(a,b)的GCD即为(b,r)的GCD (a=b * n+r)
设v为a,b的公约数
a=tv,b=qv
r=a-bn=tv-qnv=v(t-qn),所以v是r的因子;
设u为b,r的公约数
b=xu,r=yu
a=bn+r=xun+yu=u(xn+y),所以u是a的因子。
代码如下(两种方法):
- 循环
int main()
{
int a,b;
scanf("%d%d",&a,&b);
while(b)
{
int mid=a;
a=b;
b=mid%b;
}
printf("%d\n",a);
return 0;
}
- 递归
int gcd(int a,int b)
{
if(b==0)
return a;
gcd(b,a%b);
}
如有错误,欢迎指正
上一篇: 38 数字在排序数组中出现的次数(改正了二分查找的等于号)
下一篇: NOIP2016愤怒的小鸟