【杭电】[2028]Lowest Common Multiple Plus

问题描述

问题分析

11月8号写的代码……
然后这周周练出到了这一题……
-_-||
总之……再复习一遍吧~
多个数的最小公倍数
这个思路是找寻最大的数
然后不停+1+1+1+1+1
然后来寻找一个所有数都能整除的数
本来感觉会超时……然而并没有……

 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
#include<stdio.h>
int main()
{
    int i,n,s[500],m;
    while(scanf("%d",&n)!=EOF)
    {
        m=0;
        for(i=0;i<n;i++)
        {
            scanf("%d",&s[i]);
            if(m<s[i])  m=s[i];
        }
        for(i=0;i<n;i++)
        {
          if(m%s[i]!=0)
          {
              m++;
              i=-1;
          }
        }
        printf("%d\n",m);

    }
    return 0;

}

再学学这个多个数最小公倍数的求法吧
这种方法确实很粗暴感觉不好
学会了其它的再来补上

20160403补充:

前两个数的最小公倍数求出后与下一个求最小公倍数
循环这一操作最后结果就是全部的最小公倍数

需要注意的是因为先乘后除可能会溢出
所以用int需要先除后乘

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
int gcd(int a,int b) {
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
int main() {
    int n;
    while(scanf("%d",&n)!=EOF) {
        int t;
        scanf("%d",&t);
        for(int i=1; i<n; i++) {
            int t2;
            scanf("%d",&t2);
            t=t/gcd(t,t2)*t2;
        }
        printf("%d\n",t);
    }
    return 0;