第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-2 算法训练 最大最小公倍数

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-2 算法训练 最大最小公倍数

目录

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-2 算法训练 最大最小公倍数

前言

算法训练 最大最小公倍数

C语言

C++语言

Java语言

Python语言

总结

第六届——第十三届省赛题解

第六届——第十二届省赛题解

前言

        最近的一些文章都可能会很碎，写到哪里是哪里，过一阵子会具体的整理一遍，这里其它的类型题先往后排一排，因为蓝桥最后考的也就是对题目逻辑的理解能力，也就是dp分析能力了，所以就主要目标定在这里，最近的题目会很散，很多，基本上都是网罗全网的一些dp练习题进行二次训练，准备比赛的学生底子薄的先不建议看啊，当然，脑子快的例外，可以直接跳过之前的一切直接来看即可，只需要你在高中的时候数学成绩还可以那就没啥问题，其实，dp就是规律总结，我们只需要推导出对应题目的数学规律就可以直接操作，可能是一维数组，也可能是二维数组，总体来看二维数组的较多，但是如果能降为的话建议降为，因为如果降为起来你看看时间复杂度就知道咋回事了，那么在这里祝大家能无序的各种看明白，争取能帮助到大家。

算法训练 最大最小公倍数

资源限制

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

问题描述

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

输入格式

输入一个正整数N。

输出格式

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

样例输入

9

样例输出

504

数据规模与约定

1 <= N <= 10^6

题解：遇到这类问题我们最应该想到的就是欧几里得公式，直接套用，效果那个非常哇塞的，就是这个递归的用法我还不确定大家是否都理解了，就算没有理解的也不用担心，时间还是有很多的，并且这类公式不需要我们自己去推断，前人已经为我们把控好了，直接放心食用即可。

C语言

最麻烦的就是C语言，我们如果不用套公式的话就会出现这类现象，写了上百行来解决这个问题。

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10000

//输出值
void Print(char *num,int n)
{
	int i;
	for(i=n-1;i>=0;i--)
	{
		printf("%c",num[i]);
	}
	printf("");
	printf("n");
}

//对字符数组进行初始化
void Init(char *num)
{
	int i;
	for(i=0;i<MAXSIZE;i++) num[i]='0';
}

//将一个整数转换为字符类型
int TransformString(char *num,int value)
{
	int num_n=0;
	while(value)
	{
		num[num_n++]=value%10+'0';
		value/=10;
	}
	return num_n;
}

//两个大整数相乘
int Multiplication(char *num1,int num1_n,char *num2,int num2_n,char *result,int result_n)
{
	int i,j;
	int carry;
	int value;
	for(i=0;i<num2_n;i++)
	{
		carry=0;
		for(j=0;j<num1_n;j++)
		{
			value=(num2[i]-'0')*(num1[j]-'0')+(result[i+j]-'0')+carry;
			carry=value/10;
			result[i+j]=value%10+'0';
		}
		if(carry)
		{
			result[i+j]=carry+'0';
			result_n=i+j+1;
		}
		else result_n=i+j;
	}
	return result_n;
}

//判断两个数是否有公约数
int GCD(int num1,int num2)
{
	int temp;
	while(num2)
	{
		temp=num1%num2;
		num1=num2;
		num2=temp;
	}
	if(num1==1) return 1;
	else return 0;
}

//选出满足条件的值
void Select(int n)
{
	char num1[MAXSIZE];
	char num2[MAXSIZE];
	char result[MAXSIZE];
	int num1_n;
	int num2_n;
	int result_n=0;
	int n1;
	int n2;
	int n3;

	if(n%2==1)
	{
		n1=n;
		n2=n-1;
		n3=n-2;
	}
	else
	{
		n1=n;
		n2=n-1;
		n3=n-3;

		while( GCD(n1,n3)!=1 || GCD(n2,n3)!=1) n3--;
		if(n3!=n-3)
		{
			n1=n-1;
			n2=n-2;
			n3=n-3;
		}
	}
	num1_n=TransformString(num1,n1);
	num2_n=TransformString(num2,n2);
	Init(result);
	result_n=Multiplication(num1,num1_n,num2,num2_n,result,result_n);
	num1_n=TransformString(num1,n3);
	Init(num2);
	num2_n=0;
	num2_n=Multiplication(num1,num1_n,result,result_n,num2,num2_n);
	Print(num2,num2_n);
}

int main()
{
	int n;
	scanf("%d",&n);
	Select(n);
	return 0;
}

C++语言

看，这不欧几里得就来了。节约了很多的代码。

#include<iostream>
using namespace std;


//两个数的最大公约数
long long gcd(long long a,long long b)
{
    return b?gcd(b,a%b):a;
}

int main()
{
	long long n,a,b,r;
	while(cin>>n)
	{
		if(n%2==1)
			cout<<n*(n-1)*(n-2)<<endl;
		else
		{
			long long s1=(n-1)*(n-2)*(n-3);
			
			a=n*(n-1);
			while(gcd(n-2,a)!=1)n--;
			if((n-2)*a>s1)
				cout<<(n-2)*a<<endl;
			else
				cout<<s1<<endl;
		}
	}
	return 0;
} 

Java语言

由于数太大了，我们只能用BigInteger来处理，所以就比较麻烦，在这点上Java这个强类型超级不方便呢。

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String num = sc.next();
		sc.close();
		BigInteger n = new BigInteger(num);
		System.out.println(f(n));
	}

	public static BigInteger f(BigInteger n) {
		if (n.subtract(new BigInteger("3")).intValue() <= 0)
			return n.multiply(new BigInteger("2"));
		else if (n.mod(new BigInteger("2")).intValue() == 1) {
			return n.multiply(n.subtract(new BigInteger("1")).multiply(n.subtract(new BigInteger("2"))));
		} else {
			if (n.mod(new BigInteger("3")).intValue() == 0) {
				return n.subtract(new BigInteger("1"))
						.multiply(n.subtract(new BigInteger("2")).multiply(n.subtract(new BigInteger("3"))));
			} else {
				return n.multiply(n.subtract(new BigInteger("1")).multiply(n.subtract(new BigInteger("3"))));
			}
		}

	}
}

Python语言

还是Python方便，

n=int(input())
if n%2:
    print(n*(n-1)*(n-2))
else:
    if n%3:
       print(n*(n-1)*(n-3)) 
    else:
        print((n-1)*(n-2)*(n-3))

总结

这里面如果都使用欧几里得会很方便，我找到我之前写的文章，有兴趣的可以去看看，使用的就是欧几里得。【蓝桥杯Java_C组·从零开始卷】第六节(二)、蓝桥杯常用数学公式

 没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。

第六届——第十三届省赛题解

所有的题目都做了讲解，最难的有配套的视频，视频提供者是【2020级的弓家宜】先生。

第六届——第十二届省赛题解

所有题目均有题解，部分第10题非最优解，至少跑20%数据。

最后

以上就是秀丽芹菜为你收集整理的第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-2 算法训练 最大最小公倍数的全部内容，希望文章能够帮你解决第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-2 算法训练 最大最小公倍数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。