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

297

Sample Output

504210

Source

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

来源： 

 

简单题解（方法一）：

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

1 #include
       
         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
        
         0;j--)31             {32                 if(i*j*j
         
          0;k--)35                 {36                     if(i*j*k
          
           max)40                         max=x;41                 }42             }43         }44         cout<
           
            <
           
          
         
        
       

 

简单题解（方法二）：

•   找规律
•   如果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
       
         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         else25             return a*(a-1)*(a-3);26     }27     else28         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<