HDU 6441 Find Integer

  • 2018-08-27
  • 22
  • 0

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 an+bn=cn.

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},给出a和n,求b和c。

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

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

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

AC代码:

评论

还没有任何评论,你来说两句吧