一．算法名称：求多项式最大公因式。 二．算法任务：求出两多项式的最大公因式，以及对应的 ( )u x 和 ( )v x 。 三．算法原理：运用欧几里得扩展算法。 四．算法描述： 输入：两整系数多项式 ,a b ；a 的次数大于等于b 的次数。（多项式的系数属于模素 数 p 的完全剩余类，即系数属于有限域 pF ） 输出： d  gcd( , ) a b 与 ,x y ，其中 xa yb d  ；  步骤：1. 若 0b  ，则 d    ，返回 ( , , a x d x y ； 1, 0 y ) , 1, x 1   0, y x 2. 初始化： 2 2 3. 当b > 0 时执行以下操作:   , a b r  3.1 q /  0, y 1  1 , a qb x   x 2 , qx y 1   y 2 qy 1 3.2 a   , b b , r x 2  , x x 1 1  , x y 2  , y y 1 1  y 4. d   , a x , x y 2 五．算法程序：  ，返回 ( , d x y 。 ) , y 2 #include #define p 7 int x2[101]={0},x1[101]={0},y2[101]={0},y1[101]={0},c[101]={0},q[101]={0}, r[101]={0},x[101]={0},y[101]={0}; int n1=0,n2=0; void qingkong(int a[]) { for(int i=0;i<=n1;i++) a[i]=0; } int cishu(int a[]) { for(int i=n1;i>=0;i--) if(a[i]!=0) 

return i; return 0; } void chuandi(int a[],int b[]) { qingkong(b); for(int i=0;i<=cishu(a);i++) b[i]=a[i]%p; } int ni(int d) { for(int i=1;i=a2) { for(int i=a1,j=a2;i>=a1-a2;i--,j--) a[i]=(b[j]*ni(b[a2])*a[a1]-a[i])%p; c[a1-a2]=(ni(b[a2])*a[a1])%p; 

a1=cishu(a); } } void cuili(int a[],int b[]) { while(cishu(b)>=0) { Mo(a,b);chuandi(c,q);Chen(q,b);jian(a,c);chuandi(c,r);qingkong(c); Chen(q,x1);jian(x2,c); chuandi(c,x);qingkong(c);Chen(q,y1);jian(y2,c);chuandi(c,y); chuandi(b,a);chuandi(r,b);chuandi(x1,x2);chuandi(x,x1); chuandi(y1,y2);chuandi(y,y1); } printf("最大公因式："); for(int i=0;i<=cishu(a);i++) printf("%d ",a[i]); printf("\n"); printf("v(x)="); for(int j=0;j<=cishu(x2);j++) printf("%d ",x2[j]); printf("\n"); printf("u(x)="); for(int k=0;k<=cishu(y2);k++) printf("%d ",y2[k]); printf("\n"); } int main() { int a[101]={0},b[101]={0},i; x2[0]=1;y1[0]=1; printf("请输入高次多项式的次数："); scanf("%d",&n1); printf("请输入此多项式的系数（按升幂排列）："); for(i=0;i<=n1;i++) scanf("%d",&a[i]); printf("请输入低次多项式的次数："); scanf("%d",&n2); printf("请输入此多项式的系数（按升幂排列）："); for(i=0;i<=n2;i++) scanf("%d",&b[i]); mo(a,n1);mo(b,n2); if(n2==0) { printf("最大公因式："); 

for(i=0;i<=n1;i++) printf("%d ",a[i]); printf("\n"); printf("v(x)=1\n"); printf("u(x)=0\n"); } else cuili(a,b); return 0; }