[mathjax]

前言

昨天打了CCPC的网络赛，就做出来这么一道题。做到后面整个人都自闭了嘤嘤嘤，今天把这个题记录一下留个纪念吧。

题目描述

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，找到b和c使得a, b, c满足\(a^n + b^n = c^n\)。

题目分析

因为题目中给的n的范围非常大，就决定了不能直接求出具体的数字再进行比较，于是一开始我的思路是把b^n挪到右边进行因式分解，结果并没有什么卵用。
大概几分钟之后灵机一动，woc这不是费马大定理嘛！

费马大定理(Fermat’s Last Theorem)

当n>2时，关于x, y, z的不定方程
x^n + y^n = z^n
没有正整数解

知道了费马大定理再回过头看这道题，发现当n>2的时候式子没有整数解，也就是说n>2的时候全部不需要考虑，直接输出-1 -1即可。
问题简化为n=0, n=1, n=2 这三种情况。
* n = 0时：
每一项都是1，而我们都知道1 + 1 != 1，于是这种情况也是无解，直接输出-1 -1。
* n = 1时：
问题变成给出a，求b, c使得a+b=c,又因为这题是special judge,所以我们只需要给出一组解即可，我这里给出的是b=1，c=a+1这一组。
* n = 2时:
这里要求出满足\(a^2 + b^2 = c^2\)的整数解，也就自然而然想到勾股定理整数解问题，给定一个a，求出两个正整数变长的b和c，使得a, b, c构成一个直角三角形。对于这类问题的求解方法，之前参考过一篇论文讲得很详细(链接戳我)，这里先直接给出求一组特解的情况的公式：
n为偶数时:
b = \frac{(a\times a-4)}{4}
c = b + 2
        n为奇数时：

b = \frac{(a\times a-1)}{2}
c= b + 1
至此这道题基本上就算是解决了，剩下的就是用代码翻译出来了。

代码实现

后记

自闭赛令人绝望，晚上LOL又是六连跪，炉石两个小时掉一颗星，可能这两天诸事不顺吧。