HDU 6441 - Find Integer - [费马大定理][2018CCPC网络选拔赛第4题]

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6441

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

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$ (0≤n≤1e9,3≤a≤4e4)，要求你给出 $b$ 和 $c$ 满足 $a^n + b^n = c^n$。

题解：

根据费马大定理，$n > 2$ 时 $a^n + b^n = c^n$ 没有整数解，所以只需要计算 $n = 0,1,2$ 这三种情况：

1、$n = 0$，任何的正整数 $b,c$ 都无法使等式成立。

2、$n = 1$，任意取。

3、$n = 2$，$a^2 = \left( {c + b} \right)\left( {c - b} \right)$，分两种情况讨论：

　　　　　　若 $a$ 为奇数，则 $a^2$ 也为奇数，则取 $b = \frac{{a^2 - 1}}{2},c = \frac{{a^2 + 1}}{2}$；

　　　　　　若 $a$ 为偶数，则 $a^2$ 必然是 $4$ 的倍数，则取 $b = \frac{{a^2 - 4}}{4},c = \frac{{a^2 + 4}}{4}$。

AC代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a,n;

int main()

{

    int T;

    cin>>T;

    while(T--)

    {

        scanf("%lld%d",&n,&a);

        if(n== || n>) printf("-1 -1\n");

        if(n==) printf("1 %lld\n",a+);

        if(n==)

        {

            if(a%==) printf("%lld %lld\n",(a*a-)/,(a*a+)/);

            else printf("%lld %lld\n",(a*a-)/,(a*a+)/);

        }

    }

}

巴特西

HDU 6441 - Find Integer - [费马大定理][2018CCPC网络选拔赛第4题]

最新文章

热门文章