2011 第二届蓝桥杯总决赛- 第三题 求1-n 的最小公倍数（n小于101）

时间：2020-12-04 00:29:57

 一、我们先考虑 当n< 41时， 结果是可以用long long 保存的。

       【1-7】的各个数因式分解是：2，3，2*2，5，2*3，7，2*2*2；最小公倍数：2*3*2   *5*    7* 2; 

1、设【1~n-1】的最小公倍数为a[n-1],如果 a[n-1]%n=0；那么a[n]=a[n-1]；例如[1~5] 和[1~6]；

2、否则，n这个数一定含有 必须乘到 a[n-1]上 的素因子，eg：8;

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define maxn 15
int prime[maxn] = {2,3,5,7,11,13,17,19,23,29, 31,37,41,43};
int main()
{
    int n,i,j,t,k;
    long long sum[42],temp;
    sum[1]=1;sum[2]=2;
        for(k=2; k<=40; k++)
        {
            if(sum[k-1]%k)//含有多的质因子
            {   temp=sum[k-1];
                for(i=0; prime[i]<=k; i++)
                  if(k%prime[i]==0)
                  {temp=temp*prime[i];}
               sum[k]=temp;
            }
            else
            sum[k]=sum[k-1];
        }
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
       printf("%lld\n",sum[n]-1);
    }
    return 0;
}

二、考虑到1-100的最小公倍数肯定超出__int64.所以需要转化成字符串问题来解

仔细观察会发现，【1-n】的最小公倍数，是【1-n-1】的最小公倍数乘以n的所有素因子中没有被【1-n-1】包含的素因子。
例如：【1-7】的最小公倍数是2*3*2*5*7，8=2*2*2,(8中2出现3次，【1-7】的素因子中只出现2次)那么【1-8】就是2*3*2*5*7*2

思路：（1）先求出1——>n 的因子；

           （2）然后只要做一个大数乘法即可。

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
#define M 101
int factor[101];//存所有的因子；
struct  a{
  int c[43];//经输出测试，最长只有42
  int length;
  a()//构造函数
  {
     length=0;
  }
}ans[101];
void getfactor()
{
   int i,j;
   for(i=1;i<M;i++)
   {
      factor[i]=i;
      for(j=2;j<i;j++)
         if(factor[i]%factor[j]==0)
          factor[i]/=factor[j];
   }
}
void bigmulti()//高精度乘法
{
   int f=0,i,j,b;
   ans[1].c[0]=1;
   ans[1].length=1;
   for(i=2;i<=100;i++)
   {
      b=factor[i];
      for(f=0,j=0;j<ans[i-1].length;j++)
      {
         f=ans[i-1].c[j]*b+f;
         ans[i].c[j]=f%10;
         f/=10;
      }
      while(f)
      {
         ans[i].c[j]=f%10;
         f/=10;
         j++;
      }
      ans[i].length=j;
   }
}
void print(int i)//输出[1,n]的最小公倍数 ans[n]
{
   for(int j=ans[i].length-1;j>=0;j--)
      printf("%d",ans[i].c[j]);
   printf("\n");
}
int main()
{
    //freopen("ans.txt","w",stdout);
    getfactor();
    bigmulti();
    int n;
    while(cin>>n)
       print(n);
    return 0;
}

问题拓展：

1.判断1到n连续n个数的最小公倍数与1到n-1连续n-1个数的最小公倍数是否相等

思路：判断n是不是素数？ （1）如果不是素数，找到一个i<=sqrt（n）的约数，判断  gcd（（n/i)，i)==1，那么输出YES；（2）否则，是素数，那么结果是NO。

代码：

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
#define LL long long
LL gcd( LL a,LL b)
{
 return b==0?a:gcd(b,a%b);
}
int main()
{
    LL n;
    scanf("%I64d",&n);
    int flag=1;
    for(LL i=2; i*i<=n; i++)
       if(n%i==0)
        {
            LL tt=gcd((n/i),i);
            if(tt-1==0)
            {
                flag=0;
                printf("YES\n");
                break;
            }
        }
    if(flag) printf("NO\n");

   return 0;
}

2、hdu 2028  n个数的最小公倍数

思路：先求两个数的最大公约数，再求最小公倍数。

#include <cstdio>
#include <iostream>
using namespace std;
int Gcd(int  a,int b)
{
    return b==0?a:Gcd(b,a%b);
}
int main()
{
int n;
int ans,yueshu,temp;
while(cin>>n)
{
  ans=1;
  for(int i=0;i<n;i++)
  {
    scanf("%d",&temp);
    yueshu=Gcd(ans,temp);
ans=temp/yueshu*ans;//先除再乘，以防溢出
  }
  printf("%d\n",ans);
}
   return 0;
}






标签：

相关文章