HDU 3892(多項式ドメインユークリッドアルゴリズム)

タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=3892
 
題意:n個の多項式を与え、それらのモード9999983が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 
#include 
#include 
#include 
#include 

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

vector 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 poly_gcd(vector a,vector b)
{
    if(b.size() == 0) return a;
    int t = a.size() - b.size();
    vector 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= 0)
        for(LL i=p; i 1) puts("YES");
        else puts("NO");
        return;
    }
    vector 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;
}