AOJ 739 First Blood，aoj739firstblood

AOJ 739 First Blood，aoj739firstblood

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 }