Description

SillyHook要给小朋友出题了，他想，对于初学者，第一题肯定是a+b 啊，但当他出完数据后神奇地发现.in不见了，只留下了一些.out，他想还原.in，但情况实在太多了，于是他想要使得[a,b] ([a,b] 表示a,b 的最小公倍数)尽可能大。

 

Input

输入文件的第一行一个整数T 表示数据组数。

接下来T行每行一个整数n ，表示.out中的数值，即a+b=n 。

Output

共T行，每行一个整数表示最大的[a,b] 的值。

 

Sample Input

3 2 3 4

Sample Output

1 2 3

 

Data Constraint

 30%的数据满足 T<=10,n<=1000

100% 的数据满足T<=10000 ,n<=10^9

 

 

题解

• 首先，对于如果一个数是偶数，那么很显然是相邻的两个奇数的最小公倍数绝对是最大的
• 那么如果是偶数，可以用一半开始做，每次找到gcd(a,b)=1的就输出；不是的话，一个减一个加

代码

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 int t,n; 5 int gcd(int a, int b) { return !b?a:gcd(b,a%b); } 6 int main() 7 { 8     scanf("%d",&t); 9     while (t--)10     {11         scanf("%d",&n);12         if (n==1) scanf("0\n");13         for (int i=n/2;i;i--)14             if (gcd(i,n-i)==1)15             { 16                 printf("%lld\n",1ll*i*(n-i)); 17                 break; 18             }19     }20     return 0;21 }