2018 CCPC网络赛1004 HDU6441 Find Integer

未分类

题意:
给定整数$a$和$n$,构造出一组$(b,c),$满足$1\leq b,c \leq 10^9$,使$a^n+b^n=c^n$,无解输出$-1 -1.$
数据范围: $(3\leq a \leq 40000,0\leq n \leq 10^9).$

首先根据费马大定理,知道$n>2$的时候该式子无解.
显然$n=0$时该式子也无解.
当$n=1$时,即求解$a+b=c$,显然$(1,a+1)$满足条件.
最后考虑$n=2$的情况,求解$a^2=c^2-b^2=(c-b)*(c+b)$.
假设$a^2=y*x=(c-b)*(c+b)$,那么$c=\frac{x+y}{2},b=\frac{x-y}{2}$,显然还需要满足$x$与$y$同奇偶,且$x>y$.
如果$a$是奇数,那么$(x,y)=(a^2,1)$显然满足要求,此时$(b,c)=\left((a^2-1)/2),(a^2+1)/2\right)$,也满足$1\leq b,c\leq 10^9$.
如果$a$是偶数,那么同理$(x,y)=(\frac{a^2}{2},2)$显然满足要求.

$PS.$此题数据范围$a \geq 3$,但显然$1\leq a \leq 2,n=2$时式子无解.