Quotient Polynomial

本文主要是介绍Quotient Polynomial，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一次的时候理解错题意了，以为是输入与K有关。。。我也不知道我怎么想的。。。反正后来改对啦

Problem B	Quotient Polynomial
Time Limit	2 Seconds

A polynomial of degree n can be expressed as

If k is any integer then we can write:

Here q(x) is called the quotient polynomial of p(x) of degree (n-1) and r is any integer which is called the remainder.

For example, if p(x) = x³ - 7x²+ 15x - 8 and k = 3 then q(x) = x² - 4x + 3 and r = 1. Again if p(x) = x³ - 7x²+ 15x - 9 and k = 3 thenq(x) = x² - 4x + 3 and r = 0.

In this problem you have to find the quotient polynomial q(x) and the remainder r. All the input and output data will fit in 32-bit signed integer.

Input
Your program should accept an even number of lines of text. Each pair of line will represent one test case. The first line will contain an integer value for k. The second line will contain a list of integers (a_n, a_{n-1, …} a₀), which represent the set of co-efficient of a polynomialp(x). Here 1 ≤ n ≤ 10000. Input is terminated by <EOF>.

Output
For each pair of lines, your program should print exactly two lines. The first line should contain the coefficients of the quotient polynomial. Print the reminder in second line. There is a blank space before and after the ‘=’ sign. Print a blank line after the output of each test case. For exact format, follow the given sample.

Sample Input	Output for Sample Input
3 1 –7 15 –8 3 1 –7 15 –9	q(x): 1 -4 3 r = 1 q(x): 1 -4 3 r = 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <stdio.h>
#include <string.h>
int a[15000];
int b[15000];
int main()
{int k, i, j;char s;while(scanf("%d",&k)!=EOF){memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(i = 0; ; i++){scanf("%d%c",&a[i], &s);if(i==0)b[0] = a[i];else{b[i] = a[i] + k * b[i-1];}if(s=='\n') break;}printf("q(x): ");for(j = 0; j < i; j++){if(j != i - 1)printf("%d ", b[j]);elseprintf("%d\n", b[j]);}printf("r = %d\n\n", b[i]);}return 0;
}

这篇关于Quotient Polynomial的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---