HDU 6441 Find Integer(费马大定理)

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ⁿ+bⁿ=cⁿ.

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$an+bn=cn，给出a和n，求b和c。

由费马大定理可知当且仅当n=1或n=2时有解，

1. n=1:随便输出
2. n=2:已知一直角三角形的一直角边求另外两条边长
   1. a为奇数:另外一条直角边(b)长为 $\frac{a^2-1}{2}$2a2−1​
   2. a为偶数:根据a为奇数公式倒推得另一直角边(b)为 $\sqrt{2\times a+1}$2×a+1 ​

但是若a为8则 $\sqrt{2\times 8+1}=\sqrt{17}$2×8+1 ​=17 ​，其解并非正解，而a=8时的正解为6,8,10可以看做是3,4,5三个数都乘2，当a=4是 $\sqrt{2\times 4+1}=3$2×4+1 ​=3可求出另一直角边的正解，所以当 a 为偶数时不可直接求解另一只直角边，而应该首先对其除以2进行缩小，直到找到其对应的可解直角三角数，根据公式求解之后再乘以相应的倍数即可。

AC代码:

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char *argv[]) {
	int T;
	scanf("%d", &T);
	for (int Case = 1, n, a; Case <= T; ++Case) {
		scanf("%d%d", &n, &a);
		if (n == 1) {
			printf("%d %d\n", a + 1, 2 * a + 1);
		}
		else if (n == 2) {
			int cnt = 1;
			int temp = sqrt(a * 2 + 1);
			while (temp * temp != a * 2 + 1 && a % 2 == 0) {
				cnt *= 2;
				a /= 2;
				temp = sqrt(a * 2 + 1);
			}
			if (a & 1) {
				printf("%d %d\n", ((a * a - 1) / 2) * cnt, ((a * a - 1) / 2 + 1) * cnt);
			}
			else {
				printf("%d %d\n", temp * cnt, ((temp * temp - 1) / 2 + 1) * cnt);
			}
		}
		else {
			printf("-1 -1\n");
		}
	} 
	return 0;
}