Johnny and the Quadratic Equation
Time limit1sMemory limit512 MB
Decide whether a quadratic congruence modulo 2^32 has a solution in x.
- Level
Hard8 of 10
- Topics
- Number theory, Math, Bit manipulation
- Solved
- No attempts yet
Problem
Johnny just learned about quadratic equations. As an eager young programmer, he immediately wrote the following program to help with his homework:
#include<cstdio>
int main() {
unsigned int a,b,c,x=0;
scanf("%u %u %u",&a,&b,&c);
do {
if (a*x*x+b*x+c==0) {
puts("YES");
return 0;
}
x++;
} while(x);
puts("NO");
return 0;
}
Every calculation is done on unsigned 32-bit integers (that is, modulo ). The program tries every unsigned 32-bit value of in turn and prints YES as soon as it finds one with ; if no such exists it prints NO. Unfortunately this brute-force loop is far too slow, even on his brand-new gaming rig. Can you reproduce its output quickly?
Input
The first line contains an integer (), the number of test cases. Each of the next lines contains three space-separated integers , , and ().
Output
For each test case, print YES if there exists an unsigned 32-bit integer with , and NO otherwise. Print each answer on its own line, in the order the test cases are given.