程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU3892 Common Roots 多項式歐幾裡德求最大公共多項式

HDU3892 Common Roots 多項式歐幾裡德求最大公共多項式

編輯：C++入門知識

這就是數論坑的地方了把，有些題目真心偏到你無法想象，需要用到多項式歐幾裡德求多項式的最大公共多項式

題意：給你n個多項式，問他們有沒有共同的根

先分析把，假設有多項式a,b,同時又有多項式k,r，令 a = k*b +r,應題目要求，令解為0，那麼a = 0,同時b也要等於0，那麼這時候要滿足a=b=0 其實 r = 0,這時候就不需要去管k了，有沒有發現跟那個擴展歐幾裡德有點相似的方程，這時候分析一下,肯定跟a,b,r有關系，同時因為他們有共同的根，所以可以把問題轉化成b,r的問題了，這時候問題就轉化成求幾個多項式的最大公約數，其實這是個錯誤名稱，應該是求多項式的最大公共多項式

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long
#define LL __int64
#define eps 1e-8

//const ll INF=9999999999999;

#define inf 0xfffffff

using namespace std;


//vector > G;
//typedef pair P;
//vector> ::iterator iter;
//
//mapmp;
//map::iterator p;

vector G[1000 + 5];

const int MOD = 999983;

int k;

int num[1000 + 5][50 + 5];

void clear() {
    for(int i=0;i>= 1;
        a = a * a%MOD;
    }
    return ans;
}

/*多項式求最大公共項*/
vector poly_gcd(vector a,vector b) {
    if(b.size() == 0) 
        return a;
    int t = a.size() - b.size();
    vector c;
    for(int i=0;i<=t;i++) {
        ll tmp =  a[i] * quick(b[0],MOD-2)%MOD;
        for(ll j=0;j= 0) {
        for(ll i=p;i 1)
                puts(YES);
            else
                puts(NO);
            continue;
        }
        vector g = poly_gcd(G[0],G[1]);
        for(ll i=2;i 1)
            puts(YES);
        else
            puts(NO);
    }
    return 0;
}