Find Integer

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0Special 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

题解：

本题首先用到了费马大定理，即a^n+b^n≠c^n。(a,b,c∈Z，n>2)

所以当n大于2或者n为0时直接输出-1,-1，当n=1时直接输出1,a+1。

当n=2时，输出勾股数。

首先a²+b²=c²，a²=c²-b²，a²=(c+b)(c-b)。

设x=c+b，y=c-b，则a²=xy。

c=(x+y)/2，b=(x-y)/2。

当然我的方法是通过打表求得勾股数，方法有点偏暴力，即枚举x，y，然后用公式看c，b是否在范围内且为整数，当然在枚举的时候少不了剪枝，不然肯定tle。

不过后来听说根据费马大定理奇偶数列法则可。直接推出式子。

打表代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
    ll b,c;
}aa[40007];
void init(){
    memset(aa,0,sizeof(aa));
    for(ll i = 3;i<=40000;i++){
        for(ll j = 1;j<i;j++){
            if(i*i%j==0){
                ll x = j;
                ll y = i*i/j;
                if((x+y)%2==0){
                    aa[i].c=(x+y)/2;
                    aa[i].b=(y-x)/2;
                    break;
                }
            }
        }
    }
}
int main(){
    init();
    int t;
    scanf("%d",&t);
    while(t--){
        ll a,b,c,n;
        scanf("%lld%lld",&n,&a);
        if(n>2||n==0){
            printf("-1 -1\n");
            continue;
        }
        else if(n==1){
            printf("1 %lld\n",a+1);
            continue;
        }
        else{
            if(aa[a].b){
                printf("%lld %lld\n",aa[a].b,aa[a].c);
            }
            else
                printf("-1 -1\n");
        }

    }
    return 0;
}

0(1)代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll a,b,c,n;
        scanf("%lld%lld",&n,&a);
        if(n>2||n==0)
        {
            printf("-1 -1\n");
            continue;
        }
        else if(n==1)
        {
            printf("1 %lld\n",a+1);
            continue;
        }
        else
        {
            if(a%2==1&&a>1)
            {
                ll cc=(a-1)/2;
                b=2*cc*(cc+1);
                c=2*cc*(cc+1)+1;
                printf("%lld %lld\n",b,c);
            }
            else if(a%2==0&&a>2)
            {
                ll cc=a/2;
                b=cc*cc-1;
                c=cc*cc+1;
                printf("%lld %lld\n",b,c);
            }
            else{
                printf("-1 -1\n");
            }
        }

    }
    return 0;
}

推导过程：

a为任意情况

a² = c² - b²

a² = (c+b)(c-b)

a² = a² * 1

c + b = a²

c - b = 1

c = (a² + 1) / 2

b = (a² - 1) / 2

a为偶数情况：

if(a² % 2 == 0)

a² = a²/2 * 2

c + b = a²/2

c - b = 2

c = a²/4 + 1

b =a²/4 - 1

证毕