首页 > ACM题库 > HDU-杭电 > hdu 2394 Johnny and the Quadratic Equation-数论[解题报告]C++
2014
01-05

hdu 2394 Johnny and the Quadratic Equation-数论[解题报告]C++

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


对于一个二次方程a*x*x+b*x+c==0(%2^32) 给出a,b,c 问 能否找到这个x;开始想复杂了,把x各种设2^..p1^..p2^..p3^..,其实只要进行可以使分解2继续下去的x的奇偶讨论即可.

如果x=2*k 各种除以2,如果x=2*k+1,关键来了,对于这个新变量k,作为下一个讨论的对象,化简后表示成 A*k^2+B*k+C 进行下一轮 当消到32个2时 表示KO了 注意几个false的情况即可 .

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;

转自:http://www.cnblogs.com/yaoz10051538/archive/2011/10/15/2212875.html
 


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