HDU2018中国大学生程序设计竞赛网络选拔赛1004Find Integer

 

Find Integer

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0
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 an+bn=cn.

 

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>2，不可能出现b、c对应a实现a^n+b^n=c^n；

　　　如果n==2，则有当a为奇数时有规律，当a为偶数时有规律；

　　　如果n==1，情况更好判断。

 

代码实现如下（g++）：

#include <iostream>
#include <cstdio>
#define ll long long int

using namespace std;

int main()
{
    int t;
    ll z;
    ll n,a;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld %lld",&n,&a);
        if(n==1)
        {
            printf("1 %lld\n",a+1);
        }
        else if(n==2)
        {
            z=a*a;
            if(a%2)
            {
                printf("%lld %lld\n",z/2,z/2+1);
            }
            else
            {
                z = z/4;
                printf("%lld %lld\n",z-1,z+1);
            }
        }
        else
            printf("-1 -1\n");
    }
    return 0;
}