首页 > ACM题库 > HDU-杭电 > HDU 3892-Common Roots-数学相关-[解题报告]HOJ
2015
04-13

HDU 3892-Common Roots-数学相关-[解题报告]HOJ

Common Roots

问题描述 :

We have many polynomials modulo p (p is a prime number). An interesting issue would be to determine whether they have some roots in common. Notice roots we mention here are integers in modulo p system (0 <= root < p). Moreover, if the given polynomial is of order r, we will guarantee that it has r roots.
For example, we have
x^2 + 13x + 36 (mod 37)
x^3 + 14x^2 + 49x + 36 (mod 37)
If x = 33 or x = 28, both of them would give the value of 0. So 33 and 28 are the roots in common.

输入:

There are many test cases (less than1000).
In each case, the integer in the first line is n (the number of polynomials in this case). Then n lines followed. Each of them starts with an integer r (order of polynomials, r <= 50), and r + 1 integers (a(r), a(r-1) ,…, a(0)), which means the polynomial goes like:
a(r) * x^r + a(r-1) * x^(r-1) + … +a(1) * x + a(0) (mod 999983).
To make it easier, p is set to be 999983, as you see.

输出:

There are many test cases (less than1000).
In each case, the integer in the first line is n (the number of polynomials in this case). Then n lines followed. Each of them starts with an integer r (order of polynomials, r <= 50), and r + 1 integers (a(r), a(r-1) ,…, a(0)), which means the polynomial goes like:
a(r) * x^r + a(r-1) * x^(r-1) + … +a(1) * x + a(0) (mod 999983).
To make it easier, p is set to be 999983, as you see.

样例输入:

2
2 1 13 36
3 1 14 49 36

样例输出:

YES

题目:http://acm.hdu.edu.cn/showproblem.php?pid=3892

 

题意:给出n个多项式,如果它们模999983等于0的所有根中有相同的就输出“YES”,否则输出“NO”。

 

分析:假设有多项式a和多项式b,如果a = q*b + r,假设a和b有公共的根x,则取x的时候,a = q*b + r = 0且b = 0.

所以此时r也等于0. 所以a, b, r有同根x,这样a,b的问题,就变成b,r的问题了。然后就是求最大公约数问题了。

 

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <vector>

using namespace std;
typedef long long LL;
const LL MOD = 999983;

vector<LL> p[505];
int T;

LL quick_mod(LL a,LL b,LL m)
{
    LL ans = 1;
    a %= m;
    while(b)
    {
        if(b&1)
        {
            ans = ans*a%m;
            b--;
        }
        b>>=1;
        a=a*a%m;
    }
    return ans;
}

vector<LL> poly_gcd(vector<LL> a,vector<LL> b)
{
    if(b.size() == 0) return a;
    int t = a.size() - b.size();
    vector<LL> c;
    for(LL i=0; i<=t; i++)
    {
        LL tmp = a[i] * quick_mod(b[0],MOD-2,MOD) % MOD;
        for(LL j=0; j<b.size(); j++)
            a[i+j] = (a[i+j] - tmp * b[j] % MOD + MOD) % MOD;
    }
    LL p = -1;
    for(LL i=0; i<a.size(); i++)
    {
        if(a[i] != 0)
        {
            p=i;
            break;
        }
    }
    if(p >= 0)
        for(LL i=p; i<a.size(); i++)
            c.push_back(a[i]);
    return poly_gcd(b,c);
}

bool Import()
{
    LL n,t;
    if(scanf("%d",&T) == 1)
    {
        for(LL i=0;i<T;i++)
        {
            p[i].clear();
            scanf("%I64d",&n);
            for(LL j=0;j<=n;j++)
            {
                scanf("%I64d",&t);
                p[i].push_back(t);
            }
        }
        return true;
    }
    return false;
}

void Work()
{
    if(T==1)
    {
        if(p[0].size() > 1) puts("YES");
        else puts("NO");
        return;
    }
    vector<LL> v = poly_gcd(p[0],p[1]);
    LL i = 2;
    while(i < T && v.size() > 1)
    {
        v = poly_gcd(v,p[i]);
        i++;
    }
    if(v.size() > 1) puts("YES");
    else puts("NO");
}

int main()
{
    while(Import())
        Work();
    return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acdreamers/article/details/12685099


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

  3. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的