首页 > 代码库 > HDU3892 Common Roots 多项式欧几里德求最大公共多项式
HDU3892 Common Roots 多项式欧几里德求最大公共多项式
这就是数论坑的地方了把,有些题目真心偏到你无法想象,需要用到多项式欧几里德求多项式的最大公共多项式
题意:给你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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。