POJ 2527 Polynomial Remains(多项式除法)

77 阅读 0 评论 51 点赞

我是靠谱客的博主儒雅小松鼠，最近开发中收集的这篇文章主要介绍POJ 2527 Polynomial Remains(多项式除法)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

Given the polynomial
a(x) = an xn + … + a1 x + a0,

compute the remainder r(x) when a(x) is divided by xk+1.
Input

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 a0 and ending with an. The input is terminated if n = k = -1.
Output

For each case, output the coefficients of the remainder on one line, starting from the constant coefficient r0. 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
Source

Alberta Collegiate Programming Contest 2003.10.18

思路：
进行多项式除法，求其余数，从正面考虑，由高次项向底次项进行计算，人脑好计算，但编码不好实现，所以采用由底次向高次计算，总是消除最低次那项，然后高项不难理解就是a[i-k]=a[i-k]-a[i];低项自然便为了0；依次类推，当项数小于k的时候就停止运算，然后a数组中剩余的就是结果。
ac代码：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<ctype.h>
#include<stack>
#include<math.h>
#include <string>
#include<algorithm>
using namespace std;
typedef unsigned long long ULL;
int main()
{
ios::sync_with_stdio(false);cin.tie(0);
int a[10005];
int n,k;
while(cin>>n>>k&&n>=0)
{
for(int i=0;i<=n;i++)
cin>>a[i];
for(int i=n;i>=k;i--)
if(a[i])
{
a[i-k]=a[i-k]-a[i];
a[i]=0;
}
while(n>=0&&!a[n])
n--;
if(n<0)
printf("0");
for(int i=0;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
return 0;
}