UVALive 7178 Irrational Roots 多项式的根

Let n be a natural number, n ≤ 8. Consider the following equation:
x
n + cn−1x
n−1 + cn−2x
n−2 + . . . + c1x + c0 = 0
where cn−1, cn−2, . . . , c1, c0 are integers and c0 ̸= 0.
It is known that all the n roots of the equation are real numbers. We consider that each root r of
the equation satisﬁes the condition: −10 ≤ r ≤ 10. Also, there might be roots that appear more than
once.
Find the number of irrational roots of the equation (an irrational root is a root that is an irrational
number).
Input
The input ﬁle contains several test cases, each of them as described below.
The ﬁrst line of the input ﬁle contains the value of n. The second line contains the values of cn−1,
cn−2, . . . , c1, c0: each two consecutive values are separated by a single space.
Output
For each test case, print one number — number of irrational roots of the equation.
Sample Input

12 -12 -454 -373 3754 1680
Sample Output

题意：给你一个首项为1的n阶方程(n<=8)，求出方程的无理数的根；

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <iostream>

#include <cmath>

#include <queue>

#include <vector>

#define MM(a,b) memset(a,b,sizeof(a));

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

#define CT continue

#define SC scanf

ll _pow(int x,int n)

{

    ll tmp=1;

    while(n){

        if(n&1) tmp*=x;

        x*=x;

        n>>=1;

    }

    return tmp;

}

int n,ans;

ll c[14],cc[14];

void solve(int x)

{

    int h=n;

    for(int i=h;i>=0;i--) c[i]=cc[i];

    while(1)

    {

        ll tmp=0;

        for(int i=h;i>=0;i--){

            tmp+=c[i]*_pow(x,i);

        }

        if(tmp==0){

            ans--;

            if(ans==0) break;

            h--;

            for(int i=0;i<=h;i++) c[i]=c[i+1]*(i+1);

        }

        else break;

    }

}

int main()

{

    while(~SC("%d",&n))

    {

        for(int i=n-1;i>=0;i--) SC("%lld",&cc[i]);

        cc[n]=1;

        ans=n;

        for(int root=-10;root<=10;root++)

            solve(root);

        printf("%d\n",ans);

    }

    return 0;

}

　　分析：对于一个首项为1的 n阶式子,假设方程有理根是p/q（p,q互素），代入方程后，方程两边同时除以(p/q)^n；同时对两边进行对q的取余可以发现，只能q==1，才能成立。因此说明该方程的有理根只能是

整数，，，然后还要判断一下重根，对于n阶方程，共有n个根，某个根是方程的k阶根如果其让方程的0-k-1导数方程都等于0，，最后无理跟=n-有理根

参考资料：

巴特西

UVALive 7178 Irrational Roots 多项式的根

最新文章

热门文章