蓝桥杯算法训练（二）最大最小公倍数 C语言

傷城~ 2022-03-21 14:20 285阅读 0赞

# 最大最小公倍数 C语言 #

**问题描述**

已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。

**输入格式**

输入一个正整数N。

**输出格式**  
输出一个整数，表示你找到的最小公倍数。

**样例输入**  
9

**样例输出**  
504

**数据规模与约定**

1 <= N <= 106。

这道题笔者刚看的时候觉得很容易，容易的过分，直接将最大的三个数相乘就好了。

但很快便发现了错误的地方。

首先，写这道题时，我们应该先了解一下什么是最小公倍数。

直接上度娘的答案：**两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。**

笔者总结了几点有用的规律：

**1、两个整数如果互质，他们的最小公倍数是两个整数的积。**

**2、连续的两个整数必定互质。**

**3、若我们输入的 n 为奇数，那么结果为最大的三个数相乘（偶数不适用）**

注：（互质是公约数只有1的两个整数，叫做互质整数。）

所以，笔者的思路是这样的：

**1、输入一个 n 值，若 n 为奇数，直接将最大的三个数相乘，否则，我们先将1~n 中最大的两个数，即 n 和 n-1 相乘得到两个数的公倍数 temp（贪心法）。** 然后再来确定第三个数。

**2、然后继续从大到小取第三个数，这第三个数只要能和temp互质，那么temp乘上这第三个数便是我们要的结果了。**

所以代码如下（附带笔者最大能力的解析注释）：

#include <stdio.h>
    
    int huzhi(long long temp,long long a)  //判断 temp 和 a 是否互质,是返回1，否则返回0 
    { 
    	long long i;
    	int b;
    	for(i=2;i<a+1;i++)
    	{ 
    		if(temp%i==0 && a%i==0) //遍历 2~a,如果存在一个 i 值，能被 temp 和 a 同时整除，则两个数不互质，否则两数互质 
    		{ 
    			b=0;
    			break;
    		}
    		
    		else
    			b=1;
    	}
    	return b; 
    }
    
    int main() { 
    	long long n,sum;
    	int i;
    	
    	scanf("%I64d",&n);
    	
    	if(n%2!=0)
    	{ 
    		sum=n*(n-1)*(n-2);
    	} //n为奇数时，直接最后三位相乘就是最终结果 
    	
    	else
    	{ 
    		long long temp=n*(n-1);//n为偶数时，用贪心法，先将最后两个数相乘 ，再来锁定第三个数 
    		long long a=n-3;  //n为偶数，所以（n-2）和 n 有公约数 2，因此（n-2）不能用 ，所以假定第三个数为（n-3） 
    		
    		for(a=n-3;a>1;a-=2)// a-=2是为了跳过偶数 
    		{ 
    			if(huzhi(temp,a)==1) //若 temp 和 a 互质，结果为temp*a
    			{  
    				temp=temp*a;
    				break;
    			}
    		}
    		
    		sum=temp;  //将最终结果赋值给sum，这一步可简化，如，直接输出temp 
    	}	
    	
    	printf("%I64d",sum);
    	
    	return 0;
    }

虽然笔者的代码有点粗糙，还有很多改进的余地，但自认为功能基本完成了。想了一整天，解决了特殊情况，头画都掉光了T\_T

# 结果！系统只给了我60分！！！ #

我百思不得其姐啊！终于在网上找到了一份系统评分满分的（正确？）代码，代码我就不贴了，直接上链接（给其他博主刷刷阅读量）：

[https://blog.csdn.net/qq\_34845121/article/details/55061306][https_blog.csdn.net_qq_34845121_article_details_55061306]

笔者看了很久，思路确实比我的清晰厉害得多，而且，笔者的很多思路也是从这篇博文上找到的，鉴定是一枚大佬~~ 但里面的**标记三** 中，有一点我始终看不懂（不贴了，有兴趣的读者可以看一下），所以我直接检查了一下：

**根据题意，如果输入的 n=6，的话，1~6的最大最小公倍数应该为30（1 \* 5 \* 6）才对。**

**但是，那段（正确？）代码运行后，如果输入6 ，得出的结果却是60（2 \* 5 \* 6）！**

然而，2 和 6 有一个公约数2啊！

所以，笔者得出结论：最起码，这道所谓的正确代码也是有问题的！（出现的问题很可能就是我看不懂的那部分）。

而网上一个博主直接指明蓝桥杯的系统有问题！本小白无法考证。毕竟没有vipT\_T。

嗯，讲得有点乱，以上没有人身攻击的意思，如果前面提到的那个链接的博主看到我的文章，还望谅解~~

如果有大佬知道，或者笔者的代码有什么问题，恳求指正~~