codeforce453DIV2——D. GCD of Polynomials

题意

给出n(1–150).
输出两个多项式A,B从常数到最高次的系数,使得对两个多项式求gcd时,恰好经过n步得到结果.
多项式的gcd一步是指(A(x),B(x))变成(B,A mod B)的过程,且当A mod B为0时,视为得到结果B.
A mod B为多项式求余,参见 long division.
要求两个多项式的所有系数都是1,0,-1.前导系数(最高次项系数)为1,度数(最高次)不超过n,第一个多项式的度数大于第二个

分析：
这个题懵逼了好几天，题解愣是没看懂，来学校后在宿舍用笔划拉了好久终于大概是了解了是怎么回事了。
逆推一下GCD的公式：GCD(A,B)=GCD(AX+B,A)。所以可以得到An=An-1*X+An-2。但是题目中有个限制每一位的系数的绝对值不大于1。将GCD变形可以得到GCD(AX+B,A)=GCD(AX-B,A),所以在递推的时候如果系数超过1，那么相减，否则相加。

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <iostream>

 using namespace std;

 const int maxn=+;

 int a[maxn][maxn];

 int n;

 int main(){

     scanf("%d",&n);

     a[][]=;a[][]=;

     for(int i=;i<=n;i++){

         for(int j=;j<=i;j++){

             if(j>)

             a[i][j]=a[i-][j-];

             if(j<=i-){

             if(a[i][j]+a[i-][j]>)

                 a[i][j]-=a[i-][j];

             else

                 a[i][j]+=a[i-][j];

             }

         }

     }

     printf("%d\n",n);

     for(int i=;i<=n;i++){

         printf("%d ",a[n][i]);

     }

     printf("\n");

     printf("%d\n",n-);

     for(int i=;i<n;i++){

         printf("%d ",a[n-][i]);

     }

 return ;

 }

巴特西

codeforce453DIV2——D. GCD of Polynomials

最新文章

热门文章