Problem Description
There are many unsolvable problem in the world.It could be about one or about zero.But this time it is about bigger number. Given an integer n(2 <= n <= 109).We should find a pair of positive integer a, b so that a + b = n and [a, b] is as large as possible. [a, b] denote the least common multiplier of a, b.
Input
The first line contains integer T(1<= T<= 10000),denote the number of the test cases. For each test cases,the first line contains an integer n.
Output
For each test cases,print the maximum [a,b] in a line.
Sample Input
3 2 3 4
Sample Output
1 2 3
Author
WJMZBMR
Source
题意:给定一个数n,要求是找到一对数a、b,使得a+b=n,且a和b的最小公倍数要最大,求最大的最小公倍数。
思路:直接暴力查询,找出最大的值。具体看代码。时间复杂度是O(n),并不会超时。注意要用long long,会爆int。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<bitset>
#include<map>
#include<vector>
#include<stdlib.h>
using namespace std;
#define ll long long
#define eps 1e-10
#define MOD 1000000007
#define N 1000000
#define inf 1e12
ll n;
ll gcd(ll a,ll b){
return b==?a:gcd(b,a%b);
}
ll lcm(ll a,ll b){
return a*b/gcd(a,b);
}
int main()
{
ll t;
scanf("%I64d",&t);
while(t--){
scanf("%I64d",&n); ll x=n/;
ll r=gcd(x,n-x);
ll ans=x*(n-x)/r;
while(r!= && x>){
x--;
r=gcd(x,n-x);
ans=max(ans,x*(n-x)/r);
}
printf("%I64d\n",ans);
}
return ;
}