题意：给出f(x),g(x),h(x)的 （最高次幂+1）的值，以及它们的各项系数，求f(x)*g(x)/h(x)的余数。
这里多项式的系数只有1或0，因为题目要求：这里多项式的加减法是将系数相加/减后再模2，这样其实也就可以用异或运算来代替加减法。
思路：看代码吧，水题一个，主要在于把除法转化成减法，一次一次减就行。
#include <iostream> #include <stdio.h> #include <string.h> 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--; /* 原先一直WA的代码,在每次更新sum的最高次幂ls时出了错误。 int mark=0; for(int i=ls; i-d>=0; i--) { sum[i]=sum[i]^h[i-d]; 下面错误错在这里只判断了i>=d的情况， 有可能当i>=d的时候sum[i]=0,这样求出mark(也就是结果的最高次幂)为0； 但是可能有i<d的时候，有sum[i]=1,那么mark就不为0。 if(sum[i] && !mark) { mark=i; } } ls=mark; */ } printf("%d",ls+1); for(int i=ls; i>=0; i--) { printf(" %d",sum[i]); } printf(" "); } return 0; }