1.輸入兩個正整數，編程計算兩個數的最小公倍數
#include<bits/stdc++.h>
using namespace std;
long long x,y;
long long gcd(long long x,long long y){
long long r=x%y;
while(r!=0){
x=y;
y=r;
r=x%y;
}return y; //求最大公約數
}
long long dj(){
return x*y/gcd(x,y);
}
int main(){
cin>>x>>y;
cout<<dj()<<endl;
return 0;
}
2.用遞回方法求x,y兩個數的最大公約數
（1）遞回關系式:gcd(x,y)=gcd(y,x%y);
（2）遞回終止條件:gcd(x,0)=x;
#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y){
return (y==0)?x:gcd(y,x%y);
}
int main(){
int x,y;
cin>>x>>y;
cout<<gcd(x,y)<<endl;
return 0;
}
3.二進制最大公約數演算法
（1）遞回終止條件:gcd(x,x)=x;
（2）遞回關系式:
x<y時:gcd(x,y)=gcd(y,x);
x為偶數,y為偶數:gcd(x,y)=2*gcd(x/2,n/2);
x為偶數,y為奇數:gcd(x,y)=gcd(x/2,y);
x為奇數,y為偶數:gcd(x,y)=gcd(x,y/2);
x為奇數,y為奇數:gcd(x,y)=gcd(y,x-y);
#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y){
if(x==y){
return x;
}
if(x<y){
return gcd(y,x);
}
if(x&1==0) return (y&1==0)?2*gcd(x/2,y/2):gcd(x/2,y);
return (y&1==0)?gcd(x,y/2):gcd(y,x-y); // &為按位與，用來判斷奇偶性，計算機中的數字通常用二進制補碼表示，
//如果為正數，補碼與原碼相同，直接看最后一位（因為數字1的前面N位均為0，跟它做與運算，前面肯定為0），奇數為1，偶數為0，與1相與，結果不變，
}
int main(){
int x,y;
cin>>x>>y;
cout<<gcd(x,y)<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/258415.html
標籤：其他
下一篇：力扣學習day3