Gym 100818F Irrational Roots （数学）

 Irrational Roots

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=101594#problem/F

 

【题意】：

判断一个整系数高阶方程的无理根的个数。

【解题思路】：

定理：如果方程f(x)=0的系数都是整数，那么方程有理根仅能是这样的分数p/q，其分子p是方程常数项的约数，分母q是方程最高次项的约数。

这里最高次系数为1，那么有理根就一定为整数。

题目给定了根的范围，枚举整数判断是为根即可。

重根判断：求导直到导数不为0.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define LL long long
#define maxn 1100000
#define eps 1e-8
#define IN freopen("in.txt","r",stdin);
using namespace std;

int main(int argc, char const *argv[])
{
    //IN;

    int n;
    LL a[10];
    LL b[10];
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++) scanf("%I64d",&b[i]);b[0]=1;

        int ans = 0;
        for(int i=-10;i<=10;i++){
            for(int j=0;j<=n;j++) a[j]=b[j];
            LL t[10] = {0};
            LL x = 1;
            for(int j=n;j>=0;j--){
                t[j] =  a[j]*x;
                x *= i;
            }

            LL  sum = 0;
            for(int j=0;j<=n;j++) sum+=t[j];

            if(sum == 0){
                ans++;
                for(int k=0;k<n;k++){//qiudao

                    for(int j=n;j>=0;j--){
                        a[j] = a[j]*(n-j-k);
                    }
                    LL x = 1;
                    for(int j=n-k-1;j>=0;j--){
                        t[j] =  a[j]*x;
                        x *= i;
                    }

                    LL sum = 0;
                    for(int j=0;j<=n-k-1;j++) sum += t[j];
                    if(sum == 0) ans++;
                    else break;
                }
            }
        }

        printf("%d
",n-ans);
    }

    return 0;
}