51nod1419 【数学】

思路：

n<=3，就是n.

考虑n>3:

我们可以轻松证明n,n-1这两个数互质：

设gcd(n,n-1)=g，n=g*k1，n-1=g*k2;

n-(n-1)=g(k1-k2)=1;

所以 g=1.

当n,n-2互质就更好了，n*(n-1)*(n-2)最大呀。

设gcd(n,n-2)=g，n=g*k1，n-2=g*k2;

n-(n-2)=g(k1-k2)=2; 得g<=2;

很好发现，g要么是1，要么是2，

so，很容易得出答案，n是奇数的时候 answer=n*(n-1)*(n-2);

考虑n%2==0，gcd(n,n-2)=2；

这时候考虑答案有几个呢？？？

我们知道n和n-2是偶数，n-1是奇数，n-3是奇数

first answer：n*(n-1)*(n-2)/2

那我说我有一个answer应该是比这个大：n*(n-1)*(n-3)

证：(n-3)>=(n-2)/2 n>=4 满足

但是不一定成立吧？

n-3和n-1一定互质？什么时候n和n-3互质呢？

同上我们很容易知道，gcd(n,n-3)<=3，1有，2不可能（n-3是奇数啊），所以只有3了

n%3!=0的时候，那就互质了。

那么如果不互质了呢？

second answer：n*(n-1)*(n-3)/3

还有一个答案：(n-1)*(n-2)*(n-3) 这个数一定比 n*(n-1)*(n-3)/3 这个大的情况很好说明且明显小于n*(n-1)*(n-3)也很好说明：

即证明(n-2)>=n/3 => 2*n>=6 => n>=3，而这边考虑的都是n>3，所以一定满足；

而且这三个数都是两两互质。

so code:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int main()

{

	LL n;

	scanf("%lld",&n);

	if(n<=3)

		printf("%lld\n",n);

	else if(n%2==1)

	{

		printf("%lld\n",n*(n-1)*(n-2));

	}

	else if(n%3!=0)

	{

		printf("%lld\n",n*(n-1)*(n-3));

	}

	else

	{

		printf("%lld\n",(n-1)*(n-2)*(n-3));

	}

	return 0;

}

巴特西

51nod1419 【数学】

最新文章

热门文章