欧几里得算法(辗转相除法)
d能被a整除,d能被b整除————> d能被a+b整除
原理:
求两个正整数 a 和 b 的 最大公约数 d
则有 gcd(a,b) = gcd(b,a%b)
关于return后跟的三元运算符
condition ? expression_if_true : expression_if_false
这个运算符首先评估 condition
,如果 condition
为 true
,则返回 expression_if_true
的结果;如果 condition
为 false
,则返回 expression_if_false
的结果。
模板:
int gcd(int a,int b){
return b ? gcd(b,a%b) : a ;
}
完整代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int gcd(int a,int b){
return b ? gcd(b,a%b) : a ;
}
int main(){
int n;
cin>>n;
while(n--){
int a,b;
cin>>a>>b;
cout<<gcd(a,b)<<endl;
}
return 0;
}