【gcd性质】最小公倍数挑战

绝地灬酷狼 2024-03-22 09:30 31阅读 0赞

[题目-最小公倍数挑战 (51nod.com)][-_ _51nod.com]

题意：

![6a3b4ea39a0d451480358cb55741a9e0.png][]

思路：

要找到三个数使得他们的lcm尽可能大

那就让这三个数都两两互质，且三个数的积尽可能大

若n为奇数，考虑n-1和n-2

n和n-1一定互质，那么考虑n和n-2是否互质

结论是：

n为奇数时，gcd(n,n-2)=1

n为偶数时，gcd(n,n-2)=2

这是为什么呢：

![8b8fb09ef8574a848c111127ab810d13.jpeg][]

所以d要不等于1，要不等于2

当n为奇数时d=1，当n为偶数时d=2

所以当n为奇数时，答案就是n\*(n-1)\*(n-2)

当n为偶数时：

因为gcd(n,n-2)=2，所以答案就是n\*(n-1)\*(n-2)/2

但是这个不一定是答案，还有别的解比它大的

考虑n-3：

当gcd(n,n-3)=1时，答案就是n\*(n-1)\*(n-3)

gcd(n,n-3)!=1时，答案就是(n-1)\*(n-2)\*(n-3)

对于gcd(n,n-3)也有性质：

gcd(n,n-3)<=3

证明方法也类似于上图

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    int n;
    
    void solve(){
    	cin>>n;
    	if(n==1) cout<<1<<'\n';
    	else if(n==2) cout<<2<<'\n';
    	else{
    		if(n%2==1) cout<<n*(n-1)*(n-2)<<'\n';
    		else{
    			if(__gcd(n,n-3)==1) cout<<n*(n-1)*(n-3)<<'\n';
    			else cout<<(n-1)*(n-2)*(n-3)<<'\n';
    		}
    	}
    }
    signed main(){
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[-_ _51nod.com]: http://www.51nod.com/Challenge/Problem.html#problemId=1419
[6a3b4ea39a0d451480358cb55741a9e0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/38b7ea8d63a44eca8290c83872f85cb0.png
[8b8fb09ef8574a848c111127ab810d13.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/c01c9ffb54f84d46abd452b52663a8f1.png

发表评论取消回复

表情：

评论列表（有 0 条评论，31人围观）

还没有评论，来说两句吧...

相关阅读

相关【gcd性质】最小公倍数挑战

[题目-最小公倍数挑战 (51nod.com)][-_ _51nod.com] 题意： ![6a3b4ea39a0d451480358cb55741a9e0.png][]

绝地灬酷狼/ 2024年03月22日 09:30/ 0 赞/ 32 阅读

相关【gcd性质】Lcm和Gcd的构造

[题目-Lcm与Gcd构造 (51nod.com)][-Lcm_Gcd_ _51nod.com] 题意： ![8bd68069802b42819bbd3ddf6b152d6

雨点打透心脏的1/2处/ 2024年03月22日 09:23/ 0 赞/ 58 阅读

相关最小公倍数

include <iostream> include <cstdio> include <vector> include <map> i

╰+哭是因爲堅強的太久メ/ 2022年11月14日 10:24/ 0 赞/ 158 阅读

相关最小公倍数

![这里写图片描述][20160720212331293] 辗转相除法，不多说 include<stdio.h> int mud(int p,int q)

淩亂°似流年/ 2022年09月23日 14:57/ 0 赞/ 174 阅读

相关最大最小公倍数

问题描述已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。输入格式输入一个正整数N。输出格式输出一个整数，表示你找到的最小公倍数。

深藏阁楼爱情的钟/ 2022年08月02日 06:53/ 0 赞/ 238 阅读

相关最小公倍数问题

问题：正整数A和正整数B 的最小公倍数是指能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。分析： > 求最小公倍数：公式法 > 两个数

Dear 丶/ 2022年03月09日 01:05/ 0 赞/ 243 阅读

相关求两个数的最大公约数GCD与最小公倍数LCM

code import java.util.Scanner; import java.util.List; import java.util.Li

Love The Way You Lie/ 2022年02月19日 08:36/ 0 赞/ 231 阅读

相关最小公倍数

题意求1-20的最小公倍数。求两个数a，b的最小公倍数嘛，先取出其中较大的那个比如a，然后再用ka去试探能否被较小那个数整除，其中，k是从1开始的自然数 ka<a\

Myth丶恋晨/ 2022年01月27日 08:09/ 0 赞/ 246 阅读

相关零基础学算法->最大公约数(GCD)和最小公倍数(LCM)

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 欧几里德算法 'Use Euclid Me

桃扇骨/ 2022年01月14日 12:39/ 0 赞/ 212 阅读

相关最小公倍数

include<stdio.h> long long n; long long gcd( long long n,long long m )

你的名字/ 2021年11月02日 14:38/ 0 赞/ 325 阅读