First Blood（暴力加剪枝）

- 日理万妓 2022-08-01 12:27 65阅读 0赞

First Blood

Time Limit: 1000 ms   Memory Limit: 64 MB  
Total Submission: 79   Submission Accepted: 23

Description

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

Input

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

Output

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

Sample Input

<table style=""> 
 <tbody> 
  <tr> 
   <td style="border-bottom:rgb(50,100,200) 1px; border-left:rgb(50,100,200) 1px solid; padding-bottom:3px; background-color:rgb(50,100,200); padding-left:12px; padding-right:12px; font-family:Arial,Helvetica,sans-serif; color:rgb(255,255,255); font-size:14px; border-top:rgb(50,100,200) 1px solid; border-right:rgb(50,100,200) 1px solid; padding-top:3px"> Original</td> 
   <td style="border-bottom:rgb(50,100,200) 1px; border-left:rgb(50,100,200) 1px solid; padding-bottom:3px; background-color:rgb(231,237,250); padding-left:12px; padding-right:12px; font-family:Arial,Helvetica,sans-serif; color:rgb(0,0,0); font-size:14px; border-top:rgb(50,100,200) 1px solid; border-right:rgb(50,100,200) 1px solid; padding-top:3px"> Transformed</td> 
  </tr> 
 </tbody> 
</table>

2
    9
    7

Sample Output

504
    210

**暴力加剪枝，一开始我以为是数学后来发现不是的！**

#include<cstdio>
    #include<iostream>
    #include<cmath>
    using namespace std;
    long long gcd(long long n,long long m)
    {
        long long a,b,c;
        a=n,b=m;
        while(b!=0)
        {
            c=a%b;
            a=b;
            b=c;
        }
        return n*m/a;
    }
    int main()
    {
        long long t,i,j,k;
        long long n,sum,maxs,m,q;
        scanf("%lld",&t);
        while(t--)
        {
           scanf("%lld",&n);
           maxs=0;
           for(i=n;i>=1;i--)
           {
               if(i*i*i<maxs)
               {
                   break;
               }
               for(j=n;j>=1;j--)
               {
                   if(i*j*j<maxs)
                   {
                       break;
                   }
                   for(k=n;k>=1;k--)
                   {
                       if(i*j*k<maxs)
                       {
                           break;
                       }
                       m=gcd(i,gcd(j,k));
                       if(m>maxs)
                       {
                           maxs=m;
                       }
                   }
               }
           }
          printf("%lld\n",maxs);
        }
    }