2014
01-05

# Johnny and the Quadratic Equation

Johnny recently learned about this whole quadratic equation thing. Being an avid young programmer,he immediately wrote the following code that was supposed to help in 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;
}
where all calculations are performed on unsigned 32-bit integers (in other words, modulo 232). But,well, it turned out that this code runs rather slow, even on his recently updated monster gaming rig.Maybe you could help him?

The input contains several test cases. The rst line contains an integer t (t <=104) denoting the number of test cases. Then t tests follow, each of them consisting of three space separated integers a, b and c (0 <= a, b, c < 232).

The input contains several test cases. The rst line contains an integer t (t <=104) denoting the number of test cases. Then t tests follow, each of them consisting of three space separated integers a, b and c (0 <= a, b, c < 232).

3
948 43958 1429912782
95348 54988 345335
943428 4353958 3444096692

YES
NO
YES

while(true)
{
//cout<<a<<" "<<b<<" "<<" "<<c<<endl;
//system("PAUSE");
if(!(c%2))
{
//cout<<"~~~"<<endl;
if((b%2)||(a%2))
{
a*=2;
c/=2;
}
else
{
a/=2;b/=2;c/=2;
}
k--;
if(k==0)
{
break;
}
}
else
{
//cout<<"----"<<endl;
if(a%2==0&&b%2==0){temp=false;break;}
if(a%2==1&&b%2==1){temp=false;break;}
LL a1=a*2;
LL b1=2*a+b;
LL  c1=(a+b+c)/2;
a=a1;b=b1;c=c1;
k--;
if(k==0)
{
break;
}
}

}
if(temp) cout<<"YES"<<endl;
else cout<<"NO"<<endl;

1. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法