Article

2016-05-16 00:24:00

AOJ 739 First Blood

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

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

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

Sample Input
OriginalTransformed
2
9
7

Sample Output
OriginalTransformed
504
210

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



简单题解(方法一):
    - 本题可用暴力搜索法解决
    - 必须细心剪枝,否则会超时

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


简单题解(方法二):
    - 找规律
    - 如果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. long long gcd(long long a,long long b)
  4. {
  5. if(b==0)
  6. return a;
  7. return gcd(b,a%b);
  8. }
  9. bool isrp(long long m,long long n)
  10. {
  11. if(gcd(m,n)>1)
  12. return 0;
  13. else return 1;
  14. }
  15. long long lcm(long long a)
  16. {
  17. if(a%2==0)
  18. {
  19. if(!isrp(a,a-3))
  20. return lcm(a-1);
  21. else
  22. return a*(a-1)*(a-3);
  23. }
  24. else
  25. return a*(a-1)*(a-2);
  26. }
  27. int main()
  28. {
  29. int t;
  30. cin>>t;
  31. while(t--)
  32. {
  33. long long n;
  34. cin>>n;
  35. if(n==1)
  36. cout<<1<<endl;
  37. else if(n==2)
  38. cout<<2<<endl;
  39. else
  40. cout<<lcm(n)<<endl;
  41. }
  42. return 0;
  43. }



Tags:
ACM C++ 
Stats:
5 comments
202 views