[每天例题]蓝桥杯 C语言最小公倍数

hcrzhi / 2023-05-06 / 原文

最小公倍数

题目

思路分析

方法一：

建立两个for循环，第一个for循环求最小公倍数，第二个for循环进行1至n的排列

方法二：

/*
最小公倍数n项可以计算前面的n-1项
例如；1、2、3、4、5、6的最小公倍数=1、2、3、4、5的最小公倍数和6的最小公倍数
我们定义一个贡献度：贡献度（ai）%贡献度（ai-1）==0，则贡献度（ai）/=贡献度（ai-1）
若1,2,3,4,5,6等6个数求最小公倍数，则贡献度（1）=1，贡献度（2）=2，贡献度（3）=3，贡献度（4）=4/贡献度（2）=2，贡献度（5）=5，贡献度（6）=6/贡献度（3）/贡献度（2）=1
因此1,2,3,4,5,6的最小公倍数为 1*2*3*2*5*1=60
因为答案最高超过18位，所以采用高精度乘法
最后的的结果就是乘数和相应位置上的被乘数的乘积加上后一位进位
*/

代码1（方法一）

此方法超时，未成功

#include<stdio.h>
int main()
{
	long long int i,j;
	int n;
	scanf("%d",&n);
	for(i=n;;i++)//i为最小公倍数，最小公倍数首先要大于等于最大的数 
	{
		for(j=1;j<=n;j++)//序列1至n 
		{
			if(i%j!=0)//此时i不为最小公倍数 
			{
				break;
			}
			if(j>n)//j为1至n的数 
			{
				break;
			}
		}
	}
	printf("%lld",i);
	return 0;
 }

代码2

方法二与方法一的思路是一致的，只是方法二的正确率达到了50%

#include<stdio.h>
int main()
{
	long long int i,j;
	int n;
	scanf("%d",&n);
	for(i=n;;i++)
	{
		int count=0;
		for(j=1;j<=n;j++)
		{
			if(i%j==0)
			{
				count++;
			}
		}
		if(count==n)//即满足了1至n的最小公倍数 
		{
			printf("%lld",i);
			break;
		}
	 } 
	return 0;
 }

代码3（方法二）

此代码在编译软件上行得通，但是放进去验证会超时。。。

#include<stdio.h>
int main()
{
	int i,j;
	int n;
	int flag,t,jinwei;
	while(scanf("%d",&n)) 
	{
		int a[n+1];
		int lcm[1000]={0};//由于答案最大超过了long long int，故以此记录答案的每一位数字 
		lcm[0]=1;//首元素设置为1 
		for(i=1;i<=n;i++)
		{
			a[i]=i;
		}
		//求贡献度 
		for(i=4;i<=n;i++)//2,3质因数为其本身，所以从4开始分解 
		{
			for(j=2;j<=i/2;j++)//遍历从a[2]开始到a[i/2]的每一个数 
			{
				if(a[i]%a[j]==0)
				{
					a[i]/=a[j];//若a[j]为a[i]的质因数，则将a[i]分解 
				}
			}
		}
		//求完贡献度 
		jinwei=j=0;
		for(i=2;i<=n;i++)
		{
			if(a[i]!=1)//所有质因数之积则为最小公倍数，故跳过1 
			{
				flag=j; 
				j=-1;
				while(j<flag||jinwei)
				{
					j++;
					t=lcm[j]*a[i];
					lcm[j]=(t+jinwei)%10;
					jinwei=(t+jinwei)/10;
				}
			}
		}
		for(i=j;i>=0;i--)
		{
			printf("%d",lcm[i]);//输出最小公倍数 
		}
		printf("\n");
	}
	return 0;
 }