51Nod 1080 两个数的平方和

发表于 | 分类于 | 阅读次数: |
字数统计: 577 | 阅读时长 ≈ 2

1080 两个数的平方和

基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题 收藏 关注

描述

给出一个整数N，将N表示为2个整数i与j的平方之和（i <= j)，如果有多种表示，按照i的递增序输出。
例如：N = 130，130 = 3^2 + 11^2 = 7^2 + 9^2（注：3^2 + 11^2同11^2 + 3^2算1种）

Input

一个数N(1 <= N <= 10^9)

Output

共K行：每行2个数，i j，表示N = i^2 + j^2（0 <= i <= j)。
如果无法分解为2个数的平方和，则输出No Solution

Input示例

130

Output示例

3 11
7 9

题解

看到1e9的数据基本排除了暴力的可能。一个数如果能被两个数的平方和表示的话，那这两个数一定不会超过他的平方根。所以基本思路就是先给输入的这个数开方，减少数据量，枚举 0 到 sqrt(number) ，再对[0,sqrt(number)] 这个区间二分找是否存在这样的数使他的平方加上之前枚举的那个数的平方和等于number。需要注意的一点是根据在前面的个数小的顺序输出，并要去重。根据map容器的一一对应关系并且内部自动排序，可以使用map容器同时完成这两个工作。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <utility>
#define ll long long
#define ull_ unsigned long long

using namespace std ;

int n ;

int searh_Binary( int begin_ , int end_ , int num ){
    int l = begin_ , r = end_ ;
    while ( l < r ){
        int mid = ( l + r ) >> 1 ;
        int index_one = mid * mid ;
        int index_two = num * num ;
        if ( index_one + index_two == n ){
            return mid ;
        }else if ( index_one + index_two < n ){
            l = mid + 1 ;
        }else{
            r = mid ;
        }
    }
    return -1 ;
}

int main(){
    cin >> n ;
    int num = (int)sqrt(n) ;
    int index ;
    bool check = false ;
    map<int , int> map_ ;
    for ( int i = 0 ; i <= num ; i ++ ){
        index = searh_Binary( 0 , num , i ) ;
        if ( index != -1 ){
            map_[min(i , index)] = max(i , index) ;
            check = true ;
        }
    }
    if ( !check ){
        cout << "No Solution" << endl ;
    }else{
        map<int , int>::iterator it ;
        for ( it = map_.begin() ; it != map_.end() ; it ++ ){
            cout << it->first << " " << it->second << endl ;
        }
    }
    return 0 ;
}