杭电1019 Least Common Multiple【求最小公倍数】

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1019

解题思路：lcm(a,b)=a*b/gcd(a,b)

反思：最开始提交的时候WA,以为是溢出了，于是改成了long long，还是WA,于是就不明白了，于是就去看了discuss，发现应该这样来写

lcm(a,b)=a*gcd(a,b)*b;是为了以防a乘以b太大溢出，注意啊！！！！所以就先除再乘。

#include<stdio.h>

int gcd(int a,int b)

{

    int t,r;

    if(a<b)

    {

        t=a;

        a=b;

        b=t;

    }

    r=a%b;

    while(r!=0)

    {

        a=b;

        b=r;

        r=a%b;

    }

    return b;

}

int main()

{

    int ncase;

    int n;

    int a;

    scanf("%d",&ncase);

        while(ncase--)

        {

            long s=1;

            scanf("%d",&n);

            while(n--)

            {

                scanf("%d",&a);

                s=s/gcd(s,a)*a;

            }

            printf("%ld\n",s);

        }

}

巴特西

杭电1019 Least Common Multiple【求最小公倍数】

最新文章

热门文章