NYOJ-517-最小公倍数,大数啊~~~

最小公倍数

时间限制:
1000?ms ?|? 内存限制:
65535?KB

难度:
3

描述

为什么1小时有60分钟,而不是100分钟呢?这是历史上的习惯导致。但也并非纯粹的偶然:60是个优秀的数字,它的因子比较多。事实上,它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。我们希望寻找到能除尽1至n的的每个数字的最小整数m.

输入
多组测试数据(少于500组)。

每行只有一个数n(1<=n<=100).
输出
输出相应的m。
样例输入
2
3
4
样例输出
2
6
12
来源
2011蓝桥杯

?很直观的题,就是让你求能整除1~N的最小值,我们首先想到直接求N!不就可以了,但注意,题目要求的是最小,如果N等于5,那么值为60,当N为6时,所求仍为60,故只需将1~N中所有去因子数(自定义)相乘,什么叫去因子数呢,例如,10能被5和2整除,当N为10时,是不用乘以10的,再例如6,2、3已经相乘了,能同时整除2和3必定能整除6,所以也不用乘以6.。。。。。那么怎么将这种数筛选出来呢,只需要借助数组,这题的数据范围不大,但还是要用大数才能储存这个值;

? ?AC代码:

#include<bits/stdc++.h>
using namespace std;
int a[105];
int s[100];
int main()
{
    int a[105];
    int i,j,n,x;
    for(i=1;i<105;i++)
        a[i]=i;
    for(i=1; i<105; i++)
        for(j=i+1; j<105; j++)
            if(a[j]%a[i]==0)
                a[j]=a[j]/a[i];将其因子筛去;
    while(~scanf("%d",&n))
    {
        x=0;
        memset(s,sizeof(s));
        s[0]=1;
       for(i=1;i<=n;i++)
       {
           for(j=0;j<100;j++)//大数;
           {
               int c=s[j]*a[i]+x;
               s[j]=c%10;
               x=c/10;
           }
       }
       for(i=99;i>=0;i--)
        if(s[i]) break;
       for(j=i;j>=0;j--)
        printf("%d",s[j]);
       printf("\n");
    }
   return 0;
}

相关文章

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注