第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-2 算法训练 最大最小公倍数
前言
最近的一些文章都可能会很碎，写到哪里是哪里，过一阵子会具体的整理一遍，这里其它的类型题先往后排一排，因为蓝桥最后考的也就是对题目逻辑的理解能力，也就是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("\0"); 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个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
