3.3gcd——问题 A: 两情

题目描述

“只愿君心似我心，定不负相思意。”——李之仪

小W将要去和小K约会啦！

但聪（ao）明（jiao）的小K并不想让小W那么容易知道他们的约会地点。于是小W收到了一条信息：

给定两个数的和n,请你求出这两个数的最小公倍数的可能值的最大值

作为交换，如果你给出了正确答案，我将会把你和小K的约会地点告诉你。”

众所周知，小W是个数学弱渣，他只好求助数学巨佬小H，但小H并不屑于做这种简单题，于是帮助小W的任务就交给你啦！

输入

输入的第一行一个整数T表示数据组数。
接下来T行每行一个整数n，表示给定的两个数的和n。

输出

共T行，每行一个整数表示和为n的两个数的最小公倍数的可能值的最大值。

样例输入

复制样例数据

3
2
3
4

样例输出

1
2
3

提示

100%的数据满足T≤10000,n≤109

ps:两数互质最大。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){
    if(a==0) return b;
    return gcd(b%a,a);
}
int main()
{
    int n;
    scanf("%d",&n);
    ll c;
    while(n--){
        scanf("%lld",&c);
        for(ll i=c/2;i<=c;i++){
            if(gcd(i,c-i)==1){
                ll ans=i*(c-i);
                cout<<ans<<endl;
                break;
            }
        }
    }
    return 0;
}