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\n",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

轉載于:https://www.cnblogs.com/traveller-ly/p/9506007.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/249680.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/249680.shtml
英文地址，請注明出處：http://en.pswp.cn/news/249680.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！