hdu 4627 The Unsolvable Problem（暴力的搜索）-白红宇

hdu 4627 The Unsolvable Problem（暴力的搜索）

阅读量：4882 次

发布时间：2019-06-11

本文共 1617 字，大约阅读时间需要 5 分钟。

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 <= 10

⁹).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。

1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               12 #include
                
                 13 #include
                 
                  14 using namespace std;15 #define ll long long16 #define eps 1e-1017 #define MOD 100000000718 #define N 100000019 #define inf 1e1220 ll n;21 ll gcd(ll a,ll b){22 return b==0?a:gcd(b,a%b);23 }24 ll lcm(ll a,ll b){25 return a*b/gcd(a,b);26 }27 int main()28 {29 ll t;30 scanf("%I64d",&t);31 while(t--){32 scanf("%I64d",&n);33 34 ll x=n/2;35 ll r=gcd(x,n-x);36 ll ans=x*(n-x)/r;37 while(r!=1 && x>0){38 x--;39 r=gcd(x,n-x);40 ans=max(ans,x*(n-x)/r);41 }42 printf("%I64d\n",ans);43 }44 return 0;45 }

View Code

转载于:https://www.cnblogs.com/UniqueColor/p/5158343.html

你可能感兴趣的文章