4421. aplusb?

Time Limits:?1000 ms??Memory Limits:?524288 KB??Detailed Limits?? Goto ProblemSet

Description

SillyHook要給小朋友出題了，他想，對于初學(xué)者，第一題肯定是a+b 啊，但當(dāng)他出完數(shù)據(jù)后神奇地發(fā)現(xiàn).in不見了，只留下了一些.out，他想還原.in，但情況實在太多了，于是他想要使得[a,b] ([a,b] 表示a,b 的最小公倍數(shù))盡可能大。

Input

輸入文件的第一行一個整數(shù)T 表示數(shù)據(jù)組數(shù)。
接下來T行每行一個整數(shù)n ，表示.out中的數(shù)值，即a+b=n 。

Output

共T行，每行一個整數(shù)表示最大的[a,b] 的值。

Sample Input

3
2
3
4

Sample Output

1
2
3

Data Constraint

30%的數(shù)據(jù)滿足 T<=10,n<=1000
100% 的數(shù)據(jù)滿足T<=10000 ,n<=10^9 做法：實際是一道結(jié)論題，但我不會證明，我用比較暴力的方法也過了。。。 顯然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

?

轉(zhuǎn)載于:https://www.cnblogs.com/traveller-ly/p/9506007.html

總結(jié)

以上是生活随笔為你收集整理的JZOJ 4421. aplusb的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。