最大公因数和最小公倍数
tangmuchen · · 个人记录
最大公因数和最小公倍数
基本用法：
可以求出这个数的最大公因数或最小公倍数。
求最大公因数
int gcd(int a,int b){
if(a%b==0)return b;
return gcd(b,a%b);
}调用函数
int a,b;
cin>>a>>b;
cout<<gcd(a,b);求最小公倍数
long long gcd(long long a,long long b){
if(a%b==0)return b;
return gcd(b,a%b);
}
long long lcm(long long a,long long b){
return a*b/gcd(a,b);
}调用函数
long long a,b;
cin>>a>>b;
cout<<lcm(a,b);错误原因：
B4025 最大公约数
错误代码：暂没尝试。
错误原因：没用gcd函数。
正确代码
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
if(a%b==0)return b;
return gcd(b,a%b);
}
int main(){
int a,b;
cin>>a>>b;
cout<<gcd(a,b);
return 0;
} 真确思路：要用gcd函数。
B3634 最大公约数和最小公倍数
错误代码：暂没尝试。
错误原因：没用gcd函数和lcm函数。
正确代码
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b){
if(a%b==0)return b;
return gcd(b,a%b);
}
long long lcm(long long a,long long b){
return a*b/gcd(a,b);
}
int main(){
long long a,b;
cin>>a>>b;
cout<<gcd(a,b)<<" ";
cout<<lcm(a,b);
return 0;
} 真确思路：要用gcd函数和lcm函数。
P4057 [Code+#1] 晨跑
错误代码：暂没尝试。
错误原因：没用gcd函数和lcm函数。
正确代码
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b){
if(a%b==0)return b;
return gcd(b,a%b);
}
long long lcm(long long a,long long b){
return a*b/gcd(a,b);
}
int main(){
long long a,b,c;
cin>>a>>b>>c;
cout<<lcm(lcm(a,b),c);
return 0;
} 真确思路：要用gcd函数和lcm函数。
P10183 [YDOI R1] Running
错误代码：暂没尝试。
错误原因：if里面不知道填什么。
正确代码
#include<bits/stdc++.h>
using namespace std;
int n;
int a[5000005];
int w;
int main(){
cin>>n;
cin>>a[1];
w=a[1];
for (int i=2;i<=n;i++){
cin>>a[i];
w=gcd(w,a[i]);
}
if (w%2==1) cout<<-1;
else cout<<w/2;
return 0;
}