3
25
2016
1

codeforces 235A

颓颓颓。

吃费老板安利做这题。

这样的题我蛮喜欢的。

题意:要你找出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的质数为p0,p1...pk,那么有$p-1=\prod_{i=1}^{k} {p_{i}}^{a_{i}}$,而根据我们对于p的定义,$n=\prod_{i=1}^{k} {p_{i}}^{a_{i}}$,这就意味着n-1无法被p0-pk整除,这就意味着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:102000!!!FFT!!!数据范围改成10100次出给初三爷!!!

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

然后问题来了,我们发现,只有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));
}

成功艹掉陈老师

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

Category: codeforces | Tags: codeforces shi | Read Count: 1550
Avatar_small
qiancl 说:
2016年3月25日 21:32

我是第一个看的你会信?


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com