看心情填坑

颓颓颓。

吃费老板安利做这题。

这样的题我蛮喜欢的。

题意：要你找出3个小于等于n的数a、b、c，使得他们lcm最大。陈老师的题

显然找三个互质的尽可能大的数比较优，假如说其中a、b不互质的那么我们取$\frac{a} {gcd}$，b道理也是一样的。

假如说n是个奇数，那么n和n-2互质，而n和n-1，n-1和n-2一定是互质的(辗转相除可以证明)

假如n是个偶数，那么答案是max((n-1)*(n-2)*(n-3),n*(n-1)*(n-p)),p是最小的n不能整除的素数。

证明如下。

假如不选择n，那么最优解就是(n-1)*(n-2)*(n-3)，证明见n是奇数的情况。

假如选择n，那么形式就是n*(n-a)*(n-b)(a>b)，要求n和a互质，n和b互质,a-b和n-b互质，然后考虑a,b的最小值，b取1显然没有问题。我们定义小于p的质数为p₀,p₁...p_k,那么有$p-1=\prod_{i=1}^{k} {p_{i}}^{a_{i}}$，而根据我们对于p的定义,$n=\prod_{i=1}^{k} {p_{i}}^{a_{i}}$，这就意味着n-1无法被p₀-p_k整除，这就意味着n-1和p-1互质，那么a=p,b=1，就是满足n和a互质，n和b互质,a-b和n-b互质的最优解。

感觉证明很优美所以我很喜欢。

#include<cstdio>
using namespace std;
int prime[]={2,3,5,7,11,13,17,19,23};
inline long long max(long long k1,long long k2){return k1>k2?k1:k2;}
int n;
int main(){
	scanf("%d",&n);
	if(n==1){printf("1");return 0;}
	if(n==2){printf("2");return 0;}
	int k=0;
	while(n%prime[k]==0)k++;
	if(k==0)printf("%I64d",1LL*(n-1)*n*(n-2));
	else printf("%I64d",max(1LL*(n-1)*n*(n-prime[k]),1LL*(n-1)*(n-2)*(n-3)));
}

你该不会觉得这样就完了吧。

然后费老板跟我说他看了陈老师题解才会，n是奇数跟我处理方法一样。但是偶数是枚举n-50到n-1然后暴力gcd判互质，答案和(n-1)*(n-2)*(n-3)取max，然后我们就开始讨论什么样的数据范围能插掉陈老师。为什么这样是对的呢，因为p过大的时候n*(n-p)<(n-2)*(n-3)，直接输出(n-1)*(n-2)*(n-3)就可以辣。

lnj:10²⁰⁰⁰!!!FFT!!!数据范围改成10¹⁰⁰次出给初三爷!!!

好像很有道理，然后我们发现，因为枚举范围很小，所以辗转相除起来会很快，虽然我做法时间复杂度增长起来很慢,但是要做好几次高精取模。

然后问题来了，我们发现，只有p=3的时候会是n*(n-1)*(n-p)比较优，p>3都是(n-1)*(n-2)*(n-3)比较优(多项式拆开来化一下，小学生都会)，然后复杂度变成O(1*高精)辣

#include<cstdio>
using namespace std;
int n;
int main(){
	scanf("%d",&n);
	if(n==1){printf("1");return 0;}
	if(n==2){printf("2");return 0;}
	if(n&1)printf("%I64d",1LL*(n-1)*n*(n-2));
	else if(n%3)printf("%I64d",1LL*(n-1)*n*(n-3));
	else printf("%I64d",1LL*(n-1)*(n-2)*(n-3));
}

成功艹掉陈老师

后来去看那场比赛的评论发现这个最简版早就有了