JZOJ 4421. aplusb

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

Sample Output

1
2
3

Data Constraint

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

做法：实际是一道结论题，但我不会证明，我用比较暴力的方法也过了。。。

显然a和b的值越接近越好，于是把令p = n / 2 + 1，然后往后枚举，找到的第一个

gcd(i, n - i) = 1 的就是答案。

代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cmath>
 5 #define LL long long
 6 using namespace std;
 7 LL n, Q;
 8 
 9 inline LL read(){
10     LL s=0; char ch=getchar();
11     for(;ch<'0'||ch>'9';ch=getchar());
12     for(;ch>='0'&&ch<='9';s=s*10+ch-'0',ch=getchar());
13     return s;
14 }
15 
16 inline LL Gcd(LL x, LL y){
17     for (; y != 0; ){
18         swap(x, y);
19         y = y % x;
20     }
21     return x;
22 }
23 
24 
25 inline void Gets(){
26     LL p=n>>1|1;
27     for(register int i=p;i<=n;i++){
28         LL g = Gcd(i, n - i);
29         if (g==1){
30             printf("%lld
",i*(n-i));
31             return;
32         }
33     }
34 }
35 
36 int main(){
37     Q=read();
38     for(;Q--;){
39         n=read();
40         Gets();
41     }
42 }

View Code