费马大定理+快读

来源 HDU 6441 Find Integer

描述

Problem 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 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

题意是给出一个a和n,求出两个整数b、c,使得满足a^n+b^n=c^n,满足输出b、c,不满足输出-1 -1。
根据费马大定理
可知当整数n >2时,关于x, y, z的方程 x^n + y^n = z^n 没有正整数解,因此当n>2我们直接输出-1 -1,而当n=1时,也可以直接特判输出1 a+1 。而对于n等于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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<math.h>
#include<stdio.h>
#include<string.h>
//快读模板
template <typename T>inline void read(T &x){
char c;int sign=1;x=0;
do{c=getchar();if(c=='-')sign=-1;}while(c<'0'||c>'9');
do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
x*=sign;
}
//
int main()
{
int t;
int n,a,b,c;
read(t);
while(t--)
{
read(n);read(a);
if(n==1)
{
printf("1 %d\n",a+1);
}
else if(n>2 || n==0)
{
printf("-1 -1\n");
}
else
{
if(a%2==1)
{
int g=(a-1)/2;
b=2*pow(g,2)+2*g;
c=b+1;
}
else
{
int g=a/2;
b=pow(g,2)-1;
c=b+2;
}
printf("%d %d\n",b,c);
}
}
}

Donate comment here

-------------本文结束感谢您的阅读-------------