【数论】UVa 10586 - Polynomial Remains

Problem F: Polynomial Remains

Given the polynomial

　　　　　　a(x) = a_n xⁿ + ... + a₁ x + a₀,

compute the remainder r(x) when a(x) is divided by x^k+1.

The input consists of a number of cases. The first line of each case specifies the two integers n and k (0 ≤ n, k ≤ 10000). The next n+1 integers give the coefficients of a(x), starting from a₀ and ending with a_n. The input is terminated if n = k = -1.

For each case, output the coefficients of the remainder on one line, starting from the constant coefficient r₀. If the remainder is 0, print only the constant coefficient. Otherwise, print only the first d+1 coefficients for a remainder of degree d. Separate the coefficients by a single space.

You may assume that the coefficients of the remainder can be represented by 32-bit integers.

Sample Input

5 2

6 3 3 2 0 1

5 2

0 0 3 2 0 1

4 1

1 4 1 1 1

6 3

2 3 -3 4 1 0 1

1 0

5 1

0 0

7

3 5

1 2 3 4

-1 -1

Sample Output

3 2

-3 -1

-2

-1 2 -3

0

0

1 2 3 4

题意已标黄，即求出一元n次多项式除以x^k+1后的余数，若余数为0，则输出0；否则，从0次幂系数r0开始输出最后一个不为0的系数。
按照除法的模拟过程模拟即可。简单说一下模拟过程：

比如

5 2

6 3 3 2 0 1

多项式除以x^k+1后,x大于等于k的幂的系数均变为0。比如若使x^5系数变为0，则需要(x^2+1)*(6*x^3) = 6*x^5 + 6*x^3;这样就可以将原多项式的5次幂项减掉，顺带着，3次幂项系数会减6；由此规律，每抵消掉一个x次幂，其x-2次幂的系数会相应减少x次幂的系数。这样一直到使x的k次幂系数为0就好了。这样代码就很好写了。

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 using namespace std;

 const int N = ;

 int n, k, c[N], i;

 int main() {

     while (~scanf("%d%d", &n, &k) && n != - || k != -)

     {

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

             scanf("%d", &c[i]);

         for (i = n; i >= k; i--)

         {

             c[i - k] -= c[i];

             c[i] = ;

         }

         i = n;

         while (c[i] ==  && i >= ) i--;

         if (i == -) printf("0\n");

         else {

             printf("%d", c[]);

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

                 printf(" %d", c[j]);

             printf("\n");

         }

     }

     return ;

 }

巴特西

【数论】UVa 10586 - Polynomial Remains

Problem F: Polynomial Remains

Sample Input

Sample Output

最新文章

热门文章