3233 古道

 时间限制: 1 s

 空间限制: 8000 KB

 题目等级:**白银 Silver**

 [传送门](http://codevs.cn/problem/3233/)

题目描述 Description

【第2天】

小陈坐车3个小时，终于到达了风光旖旎的云水谣古道。

从它的入口开始，有N种风景，例如千年的大榕树、河上的瀑布，河边的沙滩。。。。。。

每种每隔ai米有一个，所有风景交汇在一点的地方是"最美风光“。

求小陈走到”最美风光“处至少要走多少米？

输入描述 Input Description

N

N个正整数，ai

输出描述 Output Description

最少距离

样例输入 Sample Input

3

2 4 5

样例输出 Sample Output

20

数据范围及提示 Data Size & Hint.

N<= 10.ai《=100.

分类标签 Tags

**数论**

/*

求n个数的lcm.

gcd+lcm.

定理:两个数的乘积除以两个数的gcd就是两个数的lcm.

*/

#include<iostream>

#include<cstdio>

#define MAXN 11

using namespace std;

int n,s[MAXN],x,y,sum;

int exgcd(int a,int b)

{

    if(!b)

    {

        x=1;y=0;return a;

    }

    int ans=exgcd(b,a%b);

    int tot=x;x=y;y=tot-a/b*y;

    return ans;

}

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&s[i]);

    }

    int d=exgcd(s[1],s[2]);

    sum=s[1]*s[2]/d;

    for(int i=3;i<=n;i++)

    {

        d=exgcd(sum,s[i]);

        sum=sum*(s[i]/d);

    }

    printf("%d",sum);

}