AOJ 739 First Blood

First Blood

Time Limit: 1000 ms Memory Limit: 64 MB
Total Submission: 152 Submission Accepted: 37

Description

盖伦是个小学一年级的学生，在一次数学课的时候，老师给他们出了一个难题：
老师给了一个正整数 n，需要在不大于n的范围内选择三个正整数(可以是相同的)，使它们三个的最小公倍数尽可能的大。盖伦很想第一个解决这个问题，你能帮助盖伦拿到“first blood”吗？

Input

首先是一个正整数T，表示有T组测试数据
每组测试数据是一个正整数n(1<=n<=10^6)

Output

对于每组测试数据，输出最大的最小公倍数，每个输出单独占一行

Sample Input


2
9
7

Sample Output


504
210

Source

安徽省2015年“京胜杯”大学生程序设计竞赛

来源： http://icpc.ahu.edu.cn/OJ/Problem.aspx?id=739

简单题解（方法一）：

本题可用暴力搜索法解决
必须细心剪枝，否则会超时

 1 #include<iostream>
 2 using namespace std;
 3 
 4 long long gcd(long long a,long long b)
 5 {
 6     if(b==0)
 7         return a;
 8     return gcd(b,a%b);
 9  } 
10  
11  long long lcm(long long a,long long b)
12  {
13      return a/gcd(a,b)*b;
14  }
15  
16  
17 int main()
18 {
19     int t;
20     cin>>t;
21     while(t--)
22     {
23         long long n;
24         long long x,i,j,k,max=0;
25         cin>>n;
26         for(i=n;i>0;i--)
27         {
28             if(i*i*i<max)
29                 break;
30             for(j=n;j>0;j--)
31             {
32                 if(i*j*j<max)
33                     break;
34                 for(k=n;k>0;k--)
35                 {
36                     if(i*j*k<max)
37                         break;
38                     x=lcm(i,lcm(j,k));
39                     if(x>max)
40                         max=x;
41                 }
42             }
43         }
44         cout<<max<<endl;
45     }
46     return 0;
47 }

简单题解（方法二）：

找规律
如果n为奇数，则结果是n*(n-1)*(n-2)

如果n为偶数，此时n与n-2不互质，则大部分情况的结果是n*(n-1)*(n-3)，但是还有例外（n=6,12,18,24...等数时,n与n-3不是互质的）此时结果为(n-1)*(n-2)*(n-3)
还应注意n<3的情况

 1 #include<iostream>
 2 using namespace std;
 3 
 4 long long gcd(long long a,long long b)
 5 {
 6     if(b==0)
 7         return a;
 8     return gcd(b,a%b);
 9  } 
10 
11 bool isrp(long long m,long long n)
12 {
13     if(gcd(m,n)>1)
14         return 0;
15     else return 1;
16 }
17 
18 long long lcm(long long a)
19 {
20     if(a%2==0)
21     {
22         if(!isrp(a,a-3))
23             return lcm(a-1);
24         else
25             return a*(a-1)*(a-3);
26     }
27     else
28         return a*(a-1)*(a-2);
29 }
30 
31 int main()
32 {
33     int t;
34     cin>>t;
35     while(t--)
36     {
37         long long n;
38         cin>>n;
39         if(n==1)
40             cout<<1<<endl;
41         else if(n==2)
42             cout<<2<<endl;
43         else 
44             cout<<lcm(n)<<endl;
45     }
46     return 0;
47 }