题目描述
辗转相除法
求最大公约数
设maxD(x1,x2)函数返回x1,x2的最大公约数
核心思想:maxD(a,b)=maxD(b,a%b)
过程
设有两个数a,b(a>=b),执行下面的循环操作:
原来的b=a%b,原来的a=原来的b
直到b为0
那么此时a即为a,b的最大公约数
算法
#include<iostream>
using namespace std;
#include<algorithm>
int main(void){
int n;
cin>>n;
for(int k=1;k<=n;k++){
long a,b;
cin>>a>>b;
long t;
if(b>a) t=a,a=b,b=t;//让a始终大于等于b
while(b){
t=b;
b=a%b;
a=t;
}
cout<<a<<endl;
}
}
递归算法
#include<iostream>
using namespace std;
#include<algorithm>
int gcd(int a,int b){
if(b>a){
b=a+b;
a=b-a;
b=b-a;
}
if(b) return gcd(b,a%b);//b>0
else return a;//b==0
}
int main(void){
int n,a,b;
cin>>n;
for(int i=0;i<n;i++){
cin>>a>>b;
cout<<gcd(a,b)<<endl;
}
}
补充
利用分解质因数,把两个数都分解为质因数幂的集合,然后把这两个集合取交集。
代码
#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
#include<unordered_map>
#include<math.h>
int maxgcd(int a,int b){
if(a>b){
b=a+b;
a=b-a;
b=b-a;
}
unordered_map<int,int> m,ma,mb;
for(int i=2;i<=a/i;i++){
if(a<2) break;
while(a%i==0) a/=i,ma[i]++;
}
if(a>1) ma[a]++;
for(int i=2;i<=b/i;i++){
if(b<2) break;
while(b%i==0) b/=i,mb[i]++;
}
if(b>1) mb[b]++;
for(auto x:mb){
if(ma.count(x.first)){
m[x.first]=min(x.second,(ma.find(x.first))->second);
}
}
int product=1;
for(auto x:m){
product*=pow(x.first,x.second);
}
return product;
}
int main(void){
int n;
cin>>n;
int a[n+1][2];
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++) cin>>a[i][0]>>a[i][1];
for(int i=1;i<=n;i++){
cout<<maxgcd(a[i][0],a[i][1])<<endl;
}
}