题目描述
Amy asks Mr. B problem B. Please help Mr. B to solve the following problem.
Let p = 1000000007.
Given two integers b and c, please find two integers x and y
(0≤x≤y<p)(0 \leq x \leq y < p)(0≤x≤y<p), such that
(x+y) mod p=b(x + y) \bmod p = b(x+y)modp=b
(x×y) mod p=c(x \times y) \bmod p = c(x×y)modp=c
输入描述:
The first line contains an integer t, which is the number of test cases (1 <= t <= 10).In the following t lines, each line contains two integers b and c (0 <= b, c < p).
输出描述:
For each test case, please output x, y in one line.If there is a solution, because x <= y, the solution is unique.If there is no solution, please output -1, -1
示例1
输入
复制
10
4 4
5 6
10 10
10 25
20000 100000000
0 5
3 6
220 284
0 1
1000000000 1000000000
输出
复制
2 2
2 3
-1 -1
5 5
10000 10000
474848249 525151758
352077071 647922939
448762649 551237578
-1 -1
366417496 633582504解题报告：这道题目一开始很容易就想到要去求解x-y，但是呢简单的求解根据b*b-4*c是错误的，因为咱们没有办法去判断是否存在解，后来想到了一个定理就是二次剩余定理，但是奈何实力弱，只能判断出来是否存在解的情况，没有办法去实现二次剩余定理的答案的求解，最后隔壁队给了一个能够看懂得板子，才成功得求出答案，然后因为是(x+y)%mod = b，x>=0&&x<mod y>=0&&y<mod ,所以x+y存在两种答案，一种就是 x+y=b 另一种就是(x+y)=mod+b; 使用二次剩余定理会出现两个解，所以也需要去进行讨论，一共存在四种情况，进行一下分类讨论，判定一下每组x,y的解的范围和正确性，需要非常注意的就是咱们的答案是根据(x+y)%mod=b实现的，而(x*y)%mod ==c 的条件没有使用，所以在这个判断的时候就需要去使用一下，否则就会疯狂wa，and每组解的求解的时候不需要再进行取余处理了，这个时候的解就不再是mod 的情况了，而是本身就是这个等式。ac代码：
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<algorithm>
5 #include<cmath>
6 using namespace std;
7 typedef
long long ll;
8
9 const ll mod=1e9+
7;
10
11 int t;
12 ll b,c;
13
14 ll qpow(ll a,ll b,ll p){
15 ll ans=
1;
16 while(b){
17 if(b&
1) ans=ans*a%
p;
18 a=a*a%
p;
19 b>>=
1;
20 }
21 return ans;
22 }
23 ll modsqr(ll a,ll n){
24 ll b,k,i,x;
25 if(n==
2)
return a%
n;
26 if(qpow(a,(n-
1)/
2,n) ==
1){
27 if(n%
4 ==
3){
28 x=qpow(a,(n+
1)/
4,n);
29 }
30 else{
31 for(b=
1; qpow(b,(n-
1)/
2,n) ==
1; b++
);
32 i = (n-
1)/
2;
33 k=
0;
34 while(i%
2==
0){
35 i /=
2,k /=
2;
36 if((qpow(a,i,n)*qpow(b,k,n)+
1)%n ==
0) k += (n-
1)/
2;
37 }
38 x = qpow(a,(i+
1)/
2,n)*qpow(b,k/
2,n)%
n;
39 }
40 if(x*
2 > n) x = n-
x;
41 return x;
42 }
43 return -
1;
44 }
45
46 int main()
47 {
48 cin>>
t;
49 while(t--
)
50 {
51 cin>>b>>
c;
52 ll tmp1=(b*b-
4*c+
4*mod)%
mod;
53 ll flag=
modsqr(tmp1,mod);
54 if(b*b-
4*c==
0)
55 flag=
0;
56 if(flag==-
1)
//二次剩余判断是否有解
57 {
58 cout<<
"-1 -1"<<
endl;
59 continue;
60 }
61 else
62 {
63 ll tmp=mod-
flag;
64 ll y1=(b+flag)/
2;
65 ll x1=(b-flag)/
2;
66 //cout<<x1<<" "<<y1<<endl;
67 ll y2=(b+tmp)/
2;
68 ll x2=(b-tmp)/
2;
69 ll y3=(mod+b+flag)/
2;
70 ll x3=(mod+b-flag)/
2;
71 ll y4=(
2*mod+b-flag)/
2;
72 ll x4=(b+flag)/
2;
73
74 if(x1<=y1&&x1<mod&&x1>=
0&&y1<mod&&y1>=
0&&(x1*y1)%mod==
c)
75 {
76 cout<<x1<<
" "<<y1<<
endl;
77 }
78 else if(x2<=y2&&x2<mod&&x2>=
0&&y2<mod&&y2>=
0&&(x2*y2)%mod==
c)
79 {
80 cout<<x2<<
" "<<y2<<
endl;
81 }
82 else if(x3<=y3&&x3<mod&&x3>=
0&&y3<mod&&y3>=
0&&(x3*y3)%mod==
c)
83 {
84 cout<<x3<<
" "<<y3<<
endl;
85 }
86 else if(x4<=y4&&x4<mod&&x4>=
0&&y4<mod&&y4>=
0&&(x4*y4)%mod==
c)
87 {
88 cout<<x4<<
" "<<y4<<
endl;
89 }
90 else
91 {
92 cout<<
"-1 -1"<<
endl;
93 }
94 }
95 }
96 }
