hdu 4627 The Unsolvable Problem(暴力的搜索)

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 ;
}
上一篇:python re 正则表达式[转]


下一篇:ES6中Object.assign() 方法