2018中国大学生程序设计竞赛

Find Integer

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 6597    Accepted Submission(s): 1852
Special Judge

Problem Description

people in USSS love math very much, and there is a famous math problem .

give you two integers n,a,you are required to find 2 integers b,c such that a^n+b^n=c^n.

 

Input

one line contains one integer T;(1≤T≤1000000)
next T lines contains two integers n,a;(0≤n≤1000,000,000,3≤a≤40000)

 

Output

print two integers b,c if b,c exits;(1≤b,c≤1000,000,000);
else print two integers -1 -1 instead.

 

Sample Input

1 2 3

Sample Output

4 5

题目大意：

已知 n、 a 求解方程 a^n + b^n = c^n;

解题思路：

根据费马大定理 n > 2 时无解；

n == 0 时 无解；

n == 1 时 a， 1， a+1；

n == 2 时，根据已知 a 构造一组勾股数

当 a 为 大于 4 的偶数 2*k 时：  b = k^2 - 1, c = k^2 + 1;

当 a 为 大于 1 的奇数 2*k +1 时： b = 2*k^2 + 2*k, c = 2*n^2 + 2*n + 1;

code：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#define mod 1000000007
#define INF 0x3f3f3f3f
using namespace std;

const int MAXN = 1e9;
int N, a;
int main()
{
    int T, b, c, k;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &N, &a);
        if(N>2 || N==0) printf("-1 -1
");
        else if(N==1) printf("%d %d
", 1, a+1);
        if(N==2)
        {
            if(a%2){
                k = (a-1)/2;
                b = 2*k*k+2*k;
                c = 2*k*k+2*k+1;
                printf("%d %d
", b, c);
            }
            else
            {
                k = a/2;
                b = k*k-1;
                c = k*k+1;
                printf("%d %d
", b, c);
            }
        }
    }
    return 0;
}