这就是数论坑的地方了把,有些题目真心偏到你无法想象,需要用到多项式欧几里德求多项式的最大公共多项式
题意:给你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的问题了,这时候问题就转化成求几个多项式的最大公约数,其实这是个错误名称,应该是求多项式的最大公共多项式
无齿的借用了大神的模版: 模版来自: http://blog.csdn.net/acdreamers/article/details/12685099
#include<iostream> #include<cstdio> #include<list> #include<algorithm> #include<cstring> #include<string> #include<stack> #include<map> #include<vector> #include<cmath> #include<memory.h> #include<set> #include<cctype> #define ll long long #define LL __int64 #define eps 1e-8 //const ll INF=9999999999999; #define inf 0xfffffff using namespace std; //vector<pair<int,int> > G; //typedef pair<int,int> P; //vector<pair<int,int>> ::iterator iter; // //map<ll,int>mp; //map<ll,int>::iterator p; vector<ll> G[1000 + 5]; const int MOD = 999983; int k; int num[1000 + 5][50 + 5]; void clear() { for(int i=0;i<k;i++) G[i].clear(); } ll quick(ll a,ll b) { ll ans = 1; while(b) { if(b&1) { ans = (ans * a)%MOD; b--; } b >>= 1; a = a * a%MOD; } 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(int i=0;i<=t;i++) { ll tmp = a[i] * quick(b[0],MOD-2)%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(int 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); } int main() { while(scanf("%d",&k) == 1) { clear(); for(int i=0;i<k;i++) { ll x; scanf("%I64d",&x); for(int j=0;j<x+1;j++) { ll a; scanf("%I64d",&a); G[i].push_back(a); } } if(k == 1) { if(G[0].size() > 1) puts("YES"); else puts("NO"); continue; } vector<ll> g = poly_gcd(G[0],G[1]); for(ll i=2;i<k;i++) g = poly_gcd(g,G[i]); if(g.size() > 1) puts("YES"); else puts("NO"); } return 0; }
HDU3892 Common Roots 多项式欧几里德求最大公共多项式,布布扣,bubuko.com
HDU3892 Common Roots 多项式欧几里德求最大公共多项式
原文:http://blog.csdn.net/yitiaodacaidog/article/details/24850193