題目：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1892

?

題意：求兩個多項式的最大的公共多項式。

?

#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include <vector>using namespace std;int MOD; vector<int> A,B;int quick_mod(int a,int b,int m) {int ans = 1;a %= m;while(b){if(b&1){ans = ans*a%m;b--;}b>>=1;a=a*a%m;}return ans; }vector<int> poly_gcd(vector<int> a,vector<int> b) {if(b.size() == 0) return a;int t = a.size() - b.size();vector<int> c;for(int i=0;i<=t;i++){int tmp = a[i] * quick_mod(b[0],MOD-2,MOD) % MOD;for(int j=0;j<b.size();j++)a[i+j] = (a[i+j] - tmp * b[j] % MOD + MOD) % MOD;}int p = -1;for(int i=0;i<a.size();i++){if(a[i] != 0){p=i;break;}}if(p >= 0)for(int i=p;i<a.size();i++)c.push_back(a[i]);return poly_gcd(b,c); }bool Import() {scanf("%d",&MOD);if(MOD == 0) return false;int n,m,t;A.clear();B.clear();scanf("%d",&n);for(int i=0;i<=n;i++){scanf("%d",&t);A.push_back(t);}scanf("%d",&m);for(int i=0;i<=m;i++){scanf("%d",&t);B.push_back(t);}return true; }void Work() {vector<int> v = poly_gcd(A,B);printf("%d",v.size()-1);int t = v[0];for(int i=0;i<v.size();i++){v[i] = v[i] * quick_mod(t,MOD-2,MOD) % MOD;printf(" %d",v[i]);}puts(""); }int main() {int tt = 1;while(Import()){printf("Case %d: ",tt++);Work();}return 0; }

?

總結

以上是生活随笔為你收集整理的整数域上的多项式辗转相除的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。