菜单

CCPC网络赛打铁记录 D-Find Integer

八月 26, 2018 - 算法

前言

昨天打了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又是六连跪,炉石两个小时掉一颗星,可能这两天诸事不顺吧。

标签:, ,

CCPC网络赛打铁记录 D-Find Integer》有1个想法

Jimmy Wu

在知乎看到你的评论,来你的blog来看看!真是羡慕你们这些代码大佬!

回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注