首页 > 其他 > 详细

HDU 4627 The Unsolvable Problem 解题心得

时间:2015-07-18 15:30:51      阅读:113      评论:0      收藏:0      [点我收藏+]

原题:

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 9).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
 
 
 
分析:这题暴力破解是行不通的吧,因为数据太大了 ,可以用数学方法解题,
分奇数偶数讨论,再特判一下特殊情况2
还要注意  2 <= n <= 10 9    
所以所有由n得出的数据都要用__int64去定义
 
代码如下
技术分享
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;



        

int main()
{
    int t;
    cin >> t;
    while (t--){
        __int64  n;
        cin >> n;
        __int64   ans = 0;
        if (n % 2 == 0){
            if (n == 2) 
                ans = 1;
            else{
                if ((n / 2) % 2 == 0){
                    ans = (((n / 2) - 1)* (n / 2 + 1));
                }
                else{
                        ans = (((n / 2) - 2)* (n / 2 + 2));
                }
            }
        }
        else{
            ans = (n / 2 * ((n / 2) + 1));
        }
        cout << ans << endl;
    }


    return 0;
}
View Code

 

 

HDU 4627 The Unsolvable Problem 解题心得

原文:http://www.cnblogs.com/shawn-ji/p/4656870.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!