Codeforces Round #145 (Div. 2) C

http://codeforces.com/problemset/problem/235/A

假如是奇数，肯定是n*(n-1)*(n-2)，因为奇数最小的公共因子为3.则n,至少得与(n-3)有公共因子。

假如是偶数：

1、可能是(n-1)*(n-2)*(n-3)。

或者 n*(n-1)*(n-x)。由 n*(n-1)*(n-x)>(n-1)*(n-2)*(n-3) 解出x<5。

求出。

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 __int64 n;
 7 int gcd(int a,int b)
 8 {
 9     while(b!=0)
10     {
11         int r=b;
12         b=a%b;
13         a=r;
14     }
15     return a;
16 }
17 int main()
18 {
19     while(~scanf("%I64d",&n))
20     {
21         __int64 ans=0;
22         __int64 tmp;
23         if(n==1)
24         {
25             puts("1");
26             continue;
27         }
28         if(n==2)
29         {
30             puts("2");
31             continue;
32         }
33         if(n%2==0)
34         {
35             ans=(n-1)*(n-2)*(n-3);
36 
37             tmp=n*(n-1);
38             for(int j=2;j<=5;j++)
39                 if(gcd(n,n-j)==1 && gcd(n-1,n-j)==1)
40                 {
41                     tmp*=(n-j);
42                     break;
43                 }
44                 else
45                 {
46                     if(gcd(n,n-j)!=1)
47                     {
48                         int tt=(n-j)/gcd(n,n-j);
49                         tmp*=tt;
50                         if(tmp>ans)
51                             ans=tmp;
52                         tmp=tmp/tt;
53                     }
54                     else if(gcd(n-1,n-j) !=1)
55                     {
56                         int tt=(n-j)/gcd(n-1,n-j);
57                         tmp*=tt;
58                         if(tmp>ans)
59                             ans=tmp;
60                         tmp=tmp/tt;
61                     }
62                 }
63             if(tmp>ans)
64                 ans=tmp;
65         }
66         else
67             ans=n*(n-1)*(n-2);
68         printf("%I64d\n",ans);
69     }
70     return 0;
71 }