2018中国大学生程序设计竞赛 - 网络选拔赛 1004 Find Integer

Find Integer

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0Special Judge

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 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,b,c∈Z,n>2)

所以当n大于2或者n为0时直接输出-1,-1,当n=1时直接输出1,a+1。

当n=2时,输出勾股数。

首先a²+b²=c²,a²=c²-b²,a²=(c+b)(c-b)。

设x=c+b,y=c-b,则a²=xy。

c=(x+y)/2,b=(x-y)/2。

当然我的方法是通过打表求得勾股数,方法有点偏暴力,即枚举x,y,然后用公式看c,b是否在范围内且为整数,当然在枚举的时候少不了剪枝,不然肯定tle。

不过后来听说根据费马大定理奇偶数列法则可。直接推出式子。

打表代码:

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
46
47
48
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
ll b,c;
}aa[40007];
void init(){
memset(aa,0,sizeof(aa));
for(ll i = 3;i<=40000;i++){
for(ll j = 1;j<i;j++){
if(i*i%j==0){
ll x = j;
ll y = i*i/j;
if((x+y)%2==0){
aa[i].c=(x+y)/2;
aa[i].b=(y-x)/2;
break;
}
}
}
}
}
int main(){
init();
int t;
scanf("%d",&t);
while(t--){
ll a,b,c,n;
scanf("%lld%lld",&n,&a);
if(n>2||n==0){
printf("-1 -1\n");
continue;
}
else if(n==1){
printf("1 %lld\n",a+1);
continue;
}
else{
if(aa[a].b){
printf("%lld %lld\n",aa[a].b,aa[a].c);
}
else
printf("-1 -1\n");
}

}
return 0;
}

0(1)代码:

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<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ll a,b,c,n;
scanf("%lld%lld",&n,&a);
if(n>2||n==0)
{
printf("-1 -1\n");
continue;
}
else if(n==1)
{
printf("1 %lld\n",a+1);
continue;
}
else
{
if(a%2==1&&a>1)
{
ll cc=(a-1)/2;
b=2*cc*(cc+1);
c=2*cc*(cc+1)+1;
printf("%lld %lld\n",b,c);
}
else if(a%2==0&&a>2)
{
ll cc=a/2;
b=cc*cc-1;
c=cc*cc+1;
printf("%lld %lld\n",b,c);
}
else{
printf("-1 -1\n");
}
}

}
return 0;
}

推导过程:

a为任意情况

a² = c² - b²

a² = (c+b)(c-b)

a² = a² * 1

c + b = a²

c - b = 1

c = (a² + 1) / 2

b = (a² - 1) / 2

a为偶数情况:

if(a² % 2 == 0)

a² = a²/2 * 2

c + b = a²/2

c - b = 2

c = a²/4 + 1

b =a²/4 - 1

证毕


纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!