hdu 4627 The Unsovable Proble【hdu 2013多校3署名】

リンク:
http://acm.hdu.edu.cn/showproblem.php?pid=4627
The Unsovable Proble
Time Limit：2000/1000 MS（Java/Others）    メモリLimit：32768/32768 K（Java/Others）Total Submission（s）：243    Acceepted Submission(s)：143
Problem Description
The re are many unsoluble proble in the world.It could be about one or about zro.But this time it is about biggar number.
Gven an integer n（2<=n==10
9）We shound find a pair of 
positive integer a，b so that a+b=n and[a，b]is as large as possible.[a，b]denote the least common multilier of a，b.
 
Input
The first line contains integer T（1<=T<=10000）、denote the number of the test cases.
For each test cases、the first line contains an integer n.
 
Output
For each test cases、
print the maximm[a，b] in a line.
 
Sample Input

    
    
    
    

     
     
     
     3
2
3
4
    
    
    
    

 
Sample Output

    
    
    
    

     
     
     
     1
2
3
    
    
    
    

 
ソurce
2013 Multi-University Training Conteest 3
 
件名:
             
 最大の最小公倍数を探します。
            N，a+b=Nを数えて、最大のlcm（a，b）を探します。
考え方:
           
奇数のものは適当に見られます。半分だけ取ればいいです。
        偶数のは暴力のプログラムを書いて、下表を打っても気軽に規則を見抜くことができて、半分取りました。

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;

__int64 gcd(__int64 a, __int64 b)
{
    return b == 0 ? a : gcd(b,a%b);
}

__int64 lcm(__int64 a, __int64 b){
    return a/gcd(a,b)*b;
}

int main()
{
    int T;
    __int64 n;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%I64d", &n);
        __int64 a,b;
        __int64 ans = 0,tmp1,tmp2;
        if(n&1) ans = lcm(n/2,n/2+1);
        else  
        {
            if(n == 2) ans = 1;
            else
            {
                __int64 c = n/2-1;
                tmp1 = lcm(c,n-c);
                tmp2 = lcm(c-1,(n-c+1));
                ans = max(tmp1,tmp2);
            }
        }
        printf("%I64d
", ans);
    }
    return 0;
}