山东省第八届ACM省赛 F题 quadratic equation （详解）

àì夳堔傛蜴生んèń 2022-06-10 10:40 164阅读 0赞

# quadratic equation #

# Time Limit: 2000MS Memory Limit: 131072KB #

#### Problem Description ####

With given integers *a*,*b*,*c*, you are asked to judge whether the following statement is true: "For any*x*, if*a*⋅![3898.png][]\+*b*⋅*x*\+*c*=0, then*x* is an integer."

#### Input ####

The first line contains only one integer *T*(1≤*T*≤2000), which indicates the number of test cases.  
For each test case, there is only one line containing three integers *a*,*b*,*c*(−5≤*a*,*b*,*c*≤5).

#### Output ####

or each test case, output “`YES`” if the statement is true, or “`NO`” if not.

#### Example Input ####

3
    1 4 4
    0 0 1
    1 3 1

#### Example Output ####

YES
    YES
    NO

## 解题思路： ##

题目中，judge whether the following statement is true 的意思是判断一个命题是否正确，又结合第二组测试案例 得出，这是一个涉及到命题逻辑的题目，不仅仅是 判断方程的解是否都是整数解。

设 条件 P： *a*⋅![3898.png][]\+*b*⋅*x*\+*c*=0 结论 Q：*x* is an integer

那么容易得到，

由于涉及到精度问题，白白WA了好几次，最终迫不得已，直接暴力

当有解时，sqrt(b\*b-4\*a\*c) 属于\[0, 5) 故取最大 5，-b属于\[-5, 5\] ,故分子 属于（-10， 10），-2a 属于\[-2, 10\] ,所以暴力范围 是 \[-5 ,5\] 即可。

## 下面是AC代码： g++ 0ms    ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;    //AC G++
    int T;
    int a,b,c;
    int main()
    {
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(a==0 && b==0) {
                if(c==0) printf("NO\n");  //当a==b==c==0时，所有的x都符合（无论是不是整数），所有是NO；
                else printf("YES\n");  //c!=0时，前式为错，不管后面对错，都是对的；
            }
            else if(a==0) {
                if( -c%b == 0) printf("YES\n");  // -c/b = x ,判断 X 是整数
                else printf("NO\n");
            }
            else if(b*b-4*a*c>=0) {   //方程有解
                int flag=0;
                for(int i=-5; i<=5; i++)  //直接暴力求解
                {
                    if(a*i*i+b*i+c == 0)
                        flag++;     //找到x为整数的个数；
                }
                if(b*b-4*a*c==0 && flag==1) printf("YES\n");
                else if(b*b-4*a*c>0 && flag==2) printf("YES\n");
                else printf("NO\n");
            }
            else
                printf("YES\n");  //当b*b-4*a*c<0时，前式不成了，所以一直是对的；
        }
        return 0;
    }

sdut 3898

[3898.png]: http://acm.sdut.edu.cn/image/3898.png