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：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #define mod 1000000007 6 #define INF 0x3f3f3f3f 7 using namespace std; 8  9 const int MAXN = 1e9;10 int N, a;11 int main()12 {13     int T, b, c, k;14     scanf("%d", &T);15     while(T--)16     {17         scanf("%d%d", &N, &a);18         if(N>2 || N==0) printf("-1 -1\n");19         else if(N==1) printf("%d %d\n", 1, a+1);20         if(N==2)21         {22             if(a%2){23                 k = (a-1)/2;24                 b = 2*k*k+2*k;25                 c = 2*k*k+2*k+1;26                 printf("%d %d\n", b, c);27             }28             else29             {30                 k = a/2;31                 b = k*k-1;32                 c = k*k+1;33                 printf("%d %d\n", b, c);34             }35         }36     }37     return 0;38 }