题目如下:
来源:牛客网
时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
题目描述
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) such that
(x+y) mod p==b
(x*y) mod p==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
输入
1 10 2 4 4 3 5 6 4 10 10 5 10 25 6 20000 100000000 7 0 5 8 3 6 9 220 284 10 0 1 11 1000000000 1000000000
输出
1 2 2 2 2 3 3 -1 -1 4 5 5 5 10000 10000 6 474848249 525151758 7 352077071 647922939 8 448762649 551237578 9 -1 -1 10 366417496 633582504
题解:公式法
• 这个题目是某次翻Wikipedia的时候想到的
• https://en.wikipedia.org/wiki/Quadratic_residue
• 解二次方程,核心在于求二次剩余(求平方根)
• 如果p % 4 =3,x^2 % p = a
• 那么x = ±pow(a, (p+1)/4, p)
• 然后就和一般的方程一样解就可以了
• 判断是否有解用
• https://en.wikipedia.org/wiki/Euler%27s_criterion
上代码:
1 #include<bits/stdc++.h> 2 typedef long long ll; 3 using namespace std; 4 const int mod=1e9+7; 5 ll pow_mod(ll a, ll b){ 6 ll ret = 1; 7 while(b){ 8 if(b & 1) ret = (ret * a) % mod; 9 a = (a * a) % mod; 10 b >>= 1; 11 } 12 return ret; 13 } 14 int main() { 15 ll t,b,c,x,y,a; 16 scanf("%lld",&t); 17 while(t--) 18 { 19 scanf("%lld%lld",&b,&c); 20 int now=(b*b-4*c+mod)%mod; 21 if(pow_mod(now,(mod-1)/2)==mod-1) 22 { 23 printf("-1 -1 ");continue; 24 } 25 a=pow_mod(now,(mod+1)/4); 26 x=(((a+b)*(mod+1)/2)%mod+mod)%mod; 27 y=(((b-a)*(mod+1)/2)%mod+mod)%mod; 28 if(x>y) printf("%lld %lld ",y,x); 29 else printf("%lld %lld ",x,y); 30 } 31 return 0; 32 }