HDU2028Lowest Common Multiple Plus
需要注意的是，虽然最后输出为32位整数，但是a*b可能会超出int范围（最小公倍数=a*b/a和b最大公约数）
在此提供两个写法都可以AC：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #include <stdio.h>
int gcd(int a,int b)
{
int temp;
if(a<b)
{
temp=a;
a=b;
b=temp;
}
if(b==0) return a;
else return gcd(b,a%b);
}
int main()
{
int n,s;
long long t,k;
int i;
while(scanf("%d",&n)!=EOF)
{
t=0;
k=1;
for(i=1;i<=n;i++)
{
scanf("%d",&s);
t=s*k/gcd(s,k);//s*k可能超出int范围
k=t;
}
printf("%lld\n",t);
}
return 0;
} |
第二个就是把计算顺序改下，先除再乘，即a*b/c==b/c*a，计算最大公约数的方法相同就不写了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | int main()
{
int n,s;
int t,k;
int i;
while(scanf("%d",&n)!=EOF)
{
t=0;
k=1;
for(i=1;i<=n;i++)
{
scanf("%d",&s);
t=k/gcd(s,k)*s;
k=t;
}
printf("%d\n",t);
}
return 0;
} |
Momenta公司福利 292人发布
投递理想汽车等公司10个岗位 >
