方法（無證明，lz弱渣請諒解）：

以樣例來講：(x^6 + x^4 + x^2 + x + 1) (x^7 + x + 1) modulo (x^8 + x^4 + x^3 + x + 1) = x^7 + x^6 + 1 。

(x^6 + x^4 + x^2 + x + 1) (x^7 + x + 1) =x^13 + x^11 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1 。

令a=x^13 + x^11 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1 ,b=x^8 + x^4 + x^3 + x + 1;

求a/b的余數，首先b*x^(13-8)，由于系數為0或1，所以a= ? b*(x^(13-8))異或a=x^11+x^4+x^3+1

11>8重復上述步驟:a= b*(x^(11-8))異或 a=x^7+x^6+x^5+1?

7<8得結構，因此(x^6 + x^4 + x^2 + x + 1) (x^7 + x + 1) modulo (x^8 + x^4 + x^3 + x + 1) = x^7 + x^6 + 1=?x^7+x^6+x^5+1?

主要就這個不好做，其他都好寫

#include <iostream> #include <cstdio> #include <cstring>using namespace std; const int maxn=2010; //f,g,h存儲的是多項式的系數,sum存儲的是f*g的系數以及最后余數的系數 int f[maxn],g[maxn],h[maxn],sum[maxn]; int lf,lg,lh,ls;//分別為f,g,h,sum的最高次冪//比較sum表示的多項式與h表示的多項式的大小 int compare() {if(ls<lh)return -1;if(ls>lh)return 1;for(int i=ls-1; i>=0; i--) {if(sum[i]==h[i])continue;if(sum[i]>h[i])return 1;if(sum[i]<h[i])return -1;}return 0; } int main() {int t,d;scanf("%d",&t);while(t--) {memset(h,0,sizeof(h));memset(sum,0,sizeof(sum));//將f多項式的信息存入f數組scanf("%d",&d);lf=d-1;for(int j=lf; j>=0; j--) {scanf("%d",&f[j]);}//將g多項式的信息存入g數組scanf("%d",&d);lg=d-1;for(int j=lg; j>=0; j--) {scanf("%d",&g[j]);}//將h多項式的信息存入h數組scanf("%d",&d);lh=d-1;for(int j=lh; j>=0; j--) {scanf("%d",&h[j]);}//計算f*g的多項式ls=lf+lg;for(int i=lf; i>=0; i--) {for(int j=lg; j>=0; j--) {sum[i+j]=sum[i+j]^(f[i]&g[j]);}}/*關鍵是怎么求余數，這里是先判斷sum多項式是否大于h多項式，若大于，則sum減一次h，減去后的信息存入sum中。再繼續判斷,直到sum小于h，則此時的sum為余數。總之，就是把除法改成較簡單的減法操作。*/while(compare()>=0) {d=ls-lh;for(int i=ls; i-d>=0; i--) {sum[i]=sum[i]^h[i-d];}while(ls && !sum[ls])ls--;}printf("%d",ls+1);for(int i=ls; i>=0; i--) {printf(" %d",sum[i]);}printf("\n");}return 0; }

參考http://www.cnblogs.com/chenxiwenruo/p/3332698.html

轉載于:https://www.cnblogs.com/Scale-the-heights/p/4351887.html

總結

以上是生活随笔為你收集整理的poj 1060 Modular multiplication of polynomials的全部內容，希望文章能夠幫你解決所遇到的問題。

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