网易 最小众倍数 欧几里德算法
题目描述
给定5个正整数, 它们的最小的众倍数是指的能够被其中至少三个数整除的最小正整数。 给定5个不同的正整数, 请计算输出它们的最小众倍数。
输入描述:
输入包括一行,一行中有五个各不相同的正整数a, b, c, d, e(1 ≤ a, b, c, d, e ≤ 100), 以空格分割
输出描述:
输出一个整数,表示它们的最小众倍数
示例1
输入
1 2 3 4 5
输出
4
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int num[5];
int vis[5];
int stc[3];
int top;
int maxn=1<<30;
int ans;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int lcm(int a,int b,int c)
{
int lcm1=a*b/gcd(a,b);
int lcm2=lcm1*c/gcd(lcm1,c);
return lcm2;
}
int dfs(int ith)
{
if(ith==4)
{
//cout<<stc[0]<<" "<<stc[1]<<" "<<stc[2]<<endl;
//cout<<lcm(stc[0],stc[1],stc[2])<<endl;
if(lcm(stc[0],stc[1],stc[2])<ans)
{
ans=lcm(stc[0],stc[1],stc[2]);
}
return 0;
}
for(int i=0;i<5;++i)
{
if(!vis[i])
{
vis[i]=1;
stc[top++]=num[i];
dfs(ith+1);
vis[i]=0;
top--;
}
}
return 0;
}
int main()
{
while(cin>>num[0]>>num[1]>>num[2]>>num[3]>>num[4])
{
memset(vis,0,sizeof(vis));
top=0;
ans=maxn;
dfs(1);
cout<<ans<<endl;
}
return 0;
}