Question

杭电acm2028:为什么是WA？是不是m越界了？麻烦不要改我的思路！谢谢！

我用的求n个数的最小公倍数的方法是：[a1,a2,...an]表示n个数的最小公倍数，(a1,a2,...an)表示n个数的最大公约数。然后m=a1*a2*..an;
[a1,a2,...an]=m/(m/a1,m/a2...m/an);的方法。此方法是从网上找来的。
#include <stdio.h>
typedef unsigned long UL;
UL gcd(UL a,UL b)
{
UL i,c,t;
if(a<b)
{
t=a;
a=b;
b=t;
}
if(a%b!=0)
{
for(i=1;a%b!=0;i++)
{
c=a%b;
a=b;
b=c;
}
}
else c=b;
return c;
}
void main()
{
int n,i;
UL m,t,a[100000];
UL gcd(UL a,UL b);
while(scanf("%d",&n)!=EOF)
{
m=1;
for(i=1;i<=n;i++)
{
scanf("%lu",&a[i]);
m=m*a[i];
}
for(i=1;i<=n;i++)
{
a[i]=m/a[i];
}
for(i=2;i<=n;i=i+1)
{
a[i]=gcd(a[i-1],a[i]);
}
t=m/a[n];
printf("%lu\n",t);
}
}

Answer 1

是的，结果可能会超出int型的表示范围，需要将其改为_int64型的。

追问

我已经改了，但是貌似还是不行！谢谢！

Answer 2

#include <stdio.h>
typedef unsigned long UL;
UL gcd(UL a,UL b)
{
UL i,c,t;
if(a<b)
{
t=a;
a=b;
b=t;
}
if(a%b!=0)
{
for(i=1;a%b!=0;i++)
{
c=a%b;
a=b;
b=c;
}
}
else c=b;
return c;
}
void main()
{
int n,i;
UL m,t,a[100000];
UL gcd(UL a,UL b);
while(scanf("%d",&n)!=EOF)
{
m=1;
for(i=1;i<=n;i++)
{
scanf("%lu",&a[i]);
m=m/gcd(m,a[i])*a[i];
}
printf("%lu\n",m);
}
}