2018ccpc网络预选赛1004(hdu6441) 费马大定理 问题分析 代码

问题分析

题意:已知$a^n+b^n=c^n$,给出$n$和$a$,求$b$,$c$,如果无解输出$-1$。
费马大定理

  1. $a^n+b^n=c^n$,$n>2$时无解。
  2. 当$a$为奇数时,
    $a = 2 cdot k + 1$

$c = k ^ 2 + (k + 1) ^ 2$

$b = c - 1$

当 $a$ 为偶数

$a = 2 * k + 2$

$c = 1 + (k + 1) ^ 2$

$b = c - 2$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


int () {
int T;
scanf("%d", &T);
while (T--) {
int n, a;
scanf("%d%d", &n, &a);
if (n == 0 || n > 2) {
printf("-1 -1n");
} else if (n == 1) {
printf("%d %dn", 1, a + 1);
} else {
long long b, c;
if (a & 1) {
int k = a / 2;
c = k * 1LL * k + (k + 1) * 1LL * (k + 1);
b = c - 1;
} else {
int k = (a - 2) / 2;
c = 1 + 1LL * (k + 1) * (k + 1);
b = c - 2;
}
if (b > 1e9 || c > 1e9)
printf("-1 -1n");
else
printf("%lld %lldn", b, c);
}
}
}