题解

UVa 10719 - Quotient Polynomial 解题报告

题目链接：http://uva.onlinejudge.org/external/107/10719.html

第一眼看到这道题时，感觉好像挺困难啊。但试着在纸上推一推，便发现其实还是挺好做的嘛。

因为有 p(x)=(x−k)q(x)+rp(x)=(x-k)q(x)+r，我觉得直接从等号左边往右边算很难算出来，所以我从右往左推。演算的时候，根据题目的条件，我先找一个例子来算。设：

p(x)=A1x6+B1x5+C1x4+D1x3+E1x2+F1x+G1q(x)=A2x5+B2x4+C2x3+D2x2+E2x+F2\begin{aligned} p(x) &= A_1 x^6 + B_1 x^5 + C_1 x^4 + D_1 x^3 + E_1 x^2 + F_1 x + G_1 \\ q(x) &= A_2 x^5 + B_2 x^4 + C_2 x^3 + D_2 x^2 + E_2 x + F_2 \end{aligned}

把 (x−k)q(x)+r(x-k)q(x)+r 化开，可以得到：

A1=A2B1=−kA2+B2C1=−kB2+C2D1=−kC2+D2E1=−kD2+E2F1=−kE2+F2G1=−kF2+r⟹A2=A1B2=B1+kA2C2=C1+kB2D2=D1+kC2E2=E1+kD2F2=F1+kE2r=G1+kF2\begin{aligned} A_1 &= A_2 \\ B_1 &= -kA_2 + B_2 \\ C_1 &= -kB_2 + C_2 \\ D_1 &= -kC_2 + D_2 \\ E_1 &= -kD_2 + E_2 \\ F_1 &= -kE_2 + F_2 \\ G_1 &= -kF_2 + r \end{aligned} \Longrightarrow \begin{aligned} A_2 &= A_1 \\ B_2 &= B_1 + kA_2 \\ C_2 &= C_1 + kB_2 \\ D_2 &= D_1 + kC_2 \\ E_2 &= E_1 + kD_2 \\ F_2 &= F_1 + kE_2 \\ r &= G_1 + kF_2 \\ \end{aligned}

因此，我们只要抓住 A2=A1A_2 = A_1，就可以从上往下一步步地算出所有要求的东西了。

10719.cpp
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
#include <iostream>
#include <queue>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    int k;
    while (cin >> k) {
        cin.get();	// 抛掉k后面的回车
        queue<int> p;
        for (int tmp;;) {
            cin >> tmp;
            p.push(tmp);
            if (cin.get() != ' ') break;
        }
        int q = 0;
        cout << "q(x):";
        while (p.size() > 1) {
            q = p.front() + k * q;
            cout << ' ' << q;
            p.pop();
        }
        cout << "\nr = " << p.front() + k * q << "\n\n";
    }
    return 0;
}

上面的代码中，我用了 STL 队列来保存输入的数据，这使得空间复杂度成了 O(n)O(n)。其实可以把空间复杂度降到 O(1)O(1)，不过感觉在这一题里，用队列的坏处不大，因为 n 最大只到 10000，存下它不难。