L2-018 多项式A除以B（25 分）

骑猪看日落 2022-05-23 06:39 237阅读 0赞

这仍然是一道关于A/B的题，只不过A和B都换成了多项式。你需要计算两个多项式相除的商Q和余R，其中R的阶数必须小于B的阶数。

**输入格式：**

输入分两行，每行给出一个非零多项式，先给出A，再给出B。每行的格式如下：

N e\[1\] c\[1\] ... e\[N\] c\[N\]

其中N是该多项式非零项的个数，e\[i\]是第i个非零项的指数，c\[i\]是第i个非零项的系数。各项按照指数递减的顺序给出，保证所有指数是各不相同的非负整数，所有系数是非零整数，所有整数在整型范围内。

**输出格式：**

分两行先后输出商和余，输出格式与输入格式相同，输出的系数保留小数点后1位。同行数字间以1个空格分隔，行首尾不得有多余空格。注意：零多项式是一个特殊多项式，对应输出为“000.0”。但非零多项式不能输出零系数（包括舍入后为0.0）的项。在样例中，余多项式其实有常数项“-1/27”，但因其舍入后为0.0，故不输出。

**输入样例：**

4 4 1 2 -3 1 -1 0 -1
    3 2 3 1 -2 0 1

**输出样例：**

3 2 0.3 1 0.2 0 -1.0
    1 1 -3.1

分析：（参考：[点击打开链接][Link 1]）

计算

\{\\displaystyle \{\\frac \{x^\{3\}-12x^\{2\}-42\}\{x-3\}\}.\}![\{\\frac \{x^\{3\}-12x^\{2\}-42\}\{x-3\}\}.][frac _x_3_-12x_2_-42_x-3_.]

把被除式、除式按某个字母作降幂排列，并把所缺的项用零补齐，写成以下这种形式：

\{\\displaystyle \{\\frac \{x^\{3\}-12x^\{2\}+0x-42\}\{x-3\}\}.\}![\{\\frac \{x^\{3\}-12x^\{2\}+0x-42\}\{x-3\}\}.][frac _x_3_-12x_2_0x-42_x-3_.]

然后商和余数可以这样计算：

1.  将分子的第一项除以分母的最高次项（即次数最高的项，此处为x）。结果写在横线之上(x3 ÷ x = x2).
    
    \{\\displaystyle \{ 
    
    \}\} ![\{\\begin\{matrix\}x^\{2\}\\\\\\qquad \\qquad \\quad x-3\{\\overline \{)x^\{3\}-12x^\{2\}+0x-42\}\}\\end\{matrix\}\}][begin_matrix_x_2_qquad _qquad _quad x-3_overline _x_3_-12x_2_0x-42_end_matrix]
2.  将分母乘以刚得到结果（最终商的第一项），乘积写在分子前两项之下（同类项对齐） (x2 · (x − 3) = x3 − 3x2).
    
    \{\\displaystyle \{ 
    
    \}\} ![\{\\begin\{matrix\}x^\{2\}\\\\\\qquad \\qquad \\quad x-3\{\\overline \{)x^\{3\}-12x^\{2\}+0x-42\}\}\\\\\\qquad \\;\\;x^\{3\}-3x^\{2\}\\end\{matrix\}\}][begin_matrix_x_2_qquad _qquad _quad x-3_overline _x_3_-12x_2_0x-42_qquad _x_3_-3x_2_end_matrix]
3.  从分子的相应项中减去刚得到的乘积（消去相等项，把不相等的项结合起来），结果写在下面。((x3 − 12x2) − (x3 − 3x2) = −12x2 \+ 3x2 = −9x2)然后，将分子的下一项“拿下来”。
    
    \{\\displaystyle \{ 
    
    \}\} ![\{\\begin\{matrix\}x^\{2\}\\\\\\qquad \\qquad \\quad x-3\{\\overline \{)x^\{3\}-12x^\{2\}+0x-42\}\}\\\\\\qquad \\;\\;\{\\underline \{x^\{3\}-3x^\{2\}\}\}\\\\\\qquad \\qquad \\qquad \\quad \\;-9x^\{2\}+0x\\end\{matrix\}\}][begin_matrix_x_2_qquad _qquad _quad x-3_overline _x_3_-12x_2_0x-42_qquad _underline _x_3_-3x_2_qquad _qquad _qquad _quad _-9x_2_0x_end_matrix]
4.  把减得的差当作新的被除式，重复前三步（直到余式为零或余式的次数低于除式的次数时为止．被除式=除式×商式+余式 ）
    
    \{\\displaystyle \{ 
    
    \}\} ![\{\\begin\{matrix\}\\;x^\{2\}-9x\\\\\\qquad \\quad x-3\{\\overline \{)x^\{3\}-12x^\{2\}+0x-42\}\}\\\\\\;\\;\{\\underline \{\\;\\;x^\{3\}-\\;\\;3x^\{2\}\}\}\\\\\\qquad \\qquad \\quad \\;-9x^\{2\}+0x\\\\\\qquad \\qquad \\quad \\;\{\\underline \{-9x^\{2\}+27x\}\}\\\\\\qquad \\qquad \\qquad \\qquad \\qquad -27x-42\\end\{matrix\}\}][begin_matrix_x_2_-9x_qquad _quad x-3_overline _x_3_-12x_2_0x-42_underline _x_3_-_3x_2_qquad _qquad _quad _-9x_2_0x_qquad _qquad _quad _underline _-9x_2_27x_qquad _qquad _qquad _qquad _qquad -27x-42_end_matrix]
5.  重复第四步。这次没什么可以“拿下来”了。
    
    \{\\displaystyle \{ 
    
    \}\} ![\{\\begin\{matrix\}\\qquad \\quad \\;\\,x^\{2\}\\;-9x\\quad -27\\\\\\qquad \\quad x-3\{\\overline \{)x^\{3\}-12x^\{2\}+0x-42\}\}\\\\\\;\\;\{\\underline \{\\;\\;x^\{3\}-\\;\\;3x^\{2\}\}\}\\\\\\qquad \\qquad \\quad \\;-9x^\{2\}+0x\\\\\\qquad \\qquad \\quad \\;\{\\underline \{-9x^\{2\}+27x\}\}\\\\\\qquad \\qquad \\qquad \\qquad \\qquad -27x-42\\\\\\qquad \\qquad \\qquad \\qquad \\qquad \{\\underline \{-27x+81\}\}\\\\\\qquad \\qquad \\qquad \\qquad \\qquad \\qquad \\;\\;-123\\end\{matrix\}\}][begin_matrix_qquad _quad _x_2_-9x_quad -27_qquad _quad x-3_overline _x_3_-12x_2_0x-42_underline _x_3_-_3x_2_qquad _qquad _quad _-9x_2_0x_qquad _qquad _quad _underline _-9x_2_27x_qquad _qquad _qquad _qquad _qquad -27x-42_qquad _qquad _qquad _qquad _qquad _underline _-27x_81_qquad _qquad _qquad _qquad _qquad _qquad _-123_end_matrix]

横线之上的多项式即为商，而剩下的 (−123) 就是余数。

\{\\displaystyle \{\\frac \{x^\{3\}-12x^\{2\}-42\}\{x-3\}\}=\\underbrace \{x^\{2\}-9x-27\} \_\{q(x)\}\\underbrace \{-\{\\frac \{123\}\{x-3\}\}\} \_\{r(x)/g(x)\}\}![\{\\frac \{x^\{3\}-12x^\{2\}-42\}\{x-3\}\}=\\underbrace \{x^\{2\}-9x-27\} \_\{q(x)\}\\underbrace \{-\{\\frac \{123\}\{x-3\}\}\} \_\{r(x)/g(x)\}][frac _x_3_-12x_2_-42_x-3_underbrace _x_2_-9x-27_ _q_x_underbrace _-_frac _123_x-3_ _r_x_g_x]

算数的[长除法][Link 2]可以看做以上算法的一个特殊情形，即所有 x 被替换为10的情形。

## 除法变换\[[编辑][Link 3]\] ##

使用多项式长除法可以将一个多项式写成 除数-商 的形式（经常很有用）。 考虑多项式 P(x), D(x) （(D)的次数 < (P)的次数）。 然后，对某个商多项式 Q(x) 和余数多项式 R(x) （(R)的系数 < (D)的系数），

\{\\displaystyle \{\\frac \{P(x)\}\{D(x)\}\}=Q(x)+\{\\frac \{R(x)\}\{D(x)\}\}\\implies P(x)=D(x)Q(x)+R(x).\}![\{\\frac \{P(x)\}\{D(x)\}\}=Q(x)+\{\\frac \{R(x)\}\{D(x)\}\}\\implies P(x)=D(x)Q(x)+R(x).][frac _P_x_D_x_Q_x_frac _R_x_D_x_implies P_x_D_x_Q_x_R_x_.]

这种变换叫做除法变换，是从算数等式 \{\\displaystyle \{\\mathrm \{dividend\} =\\mathrm \{divisor\} \\times \\mathrm \{quotient\} +\\mathrm \{remainder\} \}\}![\{\\mathrm \{dividend\} =\\mathrm \{divisor\} \\times \\mathrm \{quotient\} +\\mathrm \{remainder\} \}][mathrm _dividend_ _mathrm _divisor_ _times _mathrm _quotient_ _mathrm _remainder_].[\[1\]][1] 得到的。

## 应用\[[编辑][Link 4]\] ##

### 多项式的因式分解\[[编辑][Link 5]\] ###

有时某个多项式的一或多个根已知，可能是使用[有理数根定理][Link 6]得到的。如果一个\{\\displaystyle n\}![n][]次多项式 \{\\displaystyle P(x)\}![P(x)][P_x]的一个根\{\\displaystyle r\}![r][]已知，那么\{\\displaystyle P(x)\}![P(x)][P_x] 可以使用多项式长除法因式分解为\{\\displaystyle (x-r)Q(x)\}![\{\\displaystyle (x-r)Q(x)\}][displaystyle _x-r_Q_x]的形式，其中\{\\displaystyle Q(x)\}![Q(x)][Q_x]是一个\{\\displaystyle n-1\}![n-1][]次的多项式。简单来说，\{\\displaystyle Q(x)\}![Q(x)][Q_x]就是长除法的商，而又知\{\\displaystyle r\}![r][]是\{\\displaystyle P(x)\}![P(x)][P_x]的一个根、余式必定为零。

相似地，如果不止一个根是已知的，比如已知\{\\displaystyle r\}![r][]和\{\\displaystyle s\}![s][]这两个，那么可以先从\{\\displaystyle P(x)\}![P(x)][P_x]中除掉线性因子\{\\displaystyle x-r\}![\{\\displaystyle x-r\}][displaystyle x-r]得到\{\\displaystyle Q(x)\}![Q(x)][Q_x]，再从\{\\displaystyle Q(x)\}![Q(x)][Q_x]中除掉 \{\\displaystyle x-s\}![\{\\displaystyle x-s\}][displaystyle x-s]，以此类推。或者可以一次性地除掉二次因子\{\\displaystyle x^\{2\}-(r+s)x+rs\}![x^\{2\}-(r+s)x+rs][x_2_-_r_s_x_rs]。

使用这种方法，有时超过四次的多项式的所有根都可以求得，虽然这并不总是可能的。例如，如果有理数根定理可以用来求得一个五次方程的一个（比例）根，它就可以被除掉以得到一个四次商式；然后使用四次方程求根的显式公式求得剩余的根。

### 寻找多项式的切线\[[编辑][Link 7]\] ###

多项式长除法可以用来在给定点上查找给定多项式的切线方程。[\[2\]][2] 如果 R(x) 是 P(x)/(x-r)2 的余式——也即，除以 x2\-2rx+r2——那么在 x=r 处 P(x) 的切线方程是 y=R(x)，不论 r 是否是 P(x) 的根。

代码：

#include<stdio.h>
    #include<math.h>
    double a[100000],b[100000],c[100000];
    int main()
    {
        int i,j,n,m,k,t,l,Ma,Mb,numa=0,numb=0;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d",&m);
            scanf("%lf",&a[m]);
            if(i==0)
                Ma=m;
        }
        scanf("%d",&l);
        for(i=0;i<l;i++)
        {
            scanf("%d",&m);
            scanf("%lf",&b[m]);
            if(i==0)
                Mb=m;
        }
        //printf("%d %d\n",Ma,Mb);
        for(i=Ma;i>=Mb;i--)
        {
            c[i-Mb]=a[i]/b[Mb];
            for(j=Mb;j>=0;j--)
            {
                a[i+j-Mb]-=b[j]*c[i-Mb];
            }
        }
        for(i=Ma-Mb;i>=0;i--)
        {
            if(fabs(c[i])>1e-6)
            {
                if(fabs(c[i])<0.05)
                {
                    c[i]=0;
                }
                else
                {
                    numa++;
                }
            }
        }
        for(i=Mb-1;i>=0;i--)
        {
            if(fabs(a[i])>1e-6)
            {
                if(fabs(a[i])<0.05)
                {
                    a[i]=0;
                }
                else
                {
                    numb++;
                }
            }
        }
        if(numa==0)
        {
            printf("0 0 0.0\n");
        }
        else
        {
            printf("%d",numa);
            for(i=Ma-Mb;i>=0;i--)
            {
                if(fabs(c[i])>1e-6)
                {
                    printf(" %d %.1lf",i,c[i]);
                }
            }
            printf("\n");
        }
    
        if(numb==0)
        {
            printf("0 0 0.0\n");
        }
        else
        {
            printf("%d",numb);
            for(i=Mb-1;i>=0;i--)
            {
                if(fabs(a[i])>1e-6)
                {
                    printf(" %d %.1lf",i,a[i]);
                }
            }
            printf("\n");
        }
        return 0;
    }

[Link 1]: https://blog.csdn.net/zoro_n/article/details/68940874
[frac _x_3_-12x_2_-42_x-3_.]: https://wikimedia.org/api/rest_v1/media/math/render/svg/29f19059502a525f4ef8e496babda170131cc652
[frac _x_3_-12x_2_0x-42_x-3_.]: https://wikimedia.org/api/rest_v1/media/math/render/svg/6ad8b345ee27ce6463a335d3d511d16f3b5719a8
[begin_matrix_x_2_qquad _qquad _quad x-3_overline _x_3_-12x_2_0x-42_end_matrix]: https://wikimedia.org/api/rest_v1/media/math/render/svg/81ae3d136c04c9b2b7514871c88e8fd12218da29
[begin_matrix_x_2_qquad _qquad _quad x-3_overline _x_3_-12x_2_0x-42_qquad _x_3_-3x_2_end_matrix]: https://wikimedia.org/api/rest_v1/media/math/render/svg/00fbb2a675a3d207f1379572e8876a3bb38a13ef
[begin_matrix_x_2_qquad _qquad _quad x-3_overline _x_3_-12x_2_0x-42_qquad _underline _x_3_-3x_2_qquad _qquad _qquad _quad _-9x_2_0x_end_matrix]: https://wikimedia.org/api/rest_v1/media/math/render/svg/965e59a5a42cdfa1f3f1be858445dab0728fff85
[begin_matrix_x_2_-9x_qquad _quad x-3_overline _x_3_-12x_2_0x-42_underline _x_3_-_3x_2_qquad _qquad _quad _-9x_2_0x_qquad _qquad _quad _underline _-9x_2_27x_qquad _qquad _qquad _qquad _qquad -27x-42_end_matrix]: https://wikimedia.org/api/rest_v1/media/math/render/svg/2f5047daf576f89bb758696b2631103d4980cb17
[begin_matrix_qquad _quad _x_2_-9x_quad -27_qquad _quad x-3_overline _x_3_-12x_2_0x-42_underline _x_3_-_3x_2_qquad _qquad _quad _-9x_2_0x_qquad _qquad _quad _underline _-9x_2_27x_qquad _qquad _qquad _qquad _qquad -27x-42_qquad _qquad _qquad _qquad _qquad _underline _-27x_81_qquad _qquad _qquad _qquad _qquad _qquad _-123_end_matrix]: https://wikimedia.org/api/rest_v1/media/math/render/svg/773a7e381f22839ec7341de6bf87530b8c4678b5
[frac _x_3_-12x_2_-42_x-3_underbrace _x_2_-9x-27_ _q_x_underbrace _-_frac _123_x-3_ _r_x_g_x]: https://wikimedia.org/api/rest_v1/media/math/render/svg/b364bffcb5a41b63875e78541741ba27bb5d508a
[Link 2]: https://zh.wikipedia.org/wiki/%E9%95%B7%E9%99%A4%E6%B3%95
[Link 3]: https://zh.wikipedia.org/w/index.php?title=%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%95%BF%E9%99%A4%E6%B3%95&action=edit&section=2
[frac _P_x_D_x_Q_x_frac _R_x_D_x_implies P_x_D_x_Q_x_R_x_.]: https://wikimedia.org/api/rest_v1/media/math/render/svg/0da571c46ff5c7810ecd1a84aee6d93666b139d2
[mathrm _dividend_ _mathrm _divisor_ _times _mathrm _quotient_ _mathrm _remainder_]: https://wikimedia.org/api/rest_v1/media/math/render/svg/c1733a624bf02a51cdde941c3cc65fe5349ce33d
[1]: https://zh.wikipedia.org/wiki/%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%95%BF%E9%99%A4%E6%B3%95#cite_note-1
[Link 4]: https://zh.wikipedia.org/w/index.php?title=%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%95%BF%E9%99%A4%E6%B3%95&action=edit&section=3
[Link 5]: https://zh.wikipedia.org/w/index.php?title=%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%95%BF%E9%99%A4%E6%B3%95&action=edit&section=4
[Link 6]: https://en.wikipedia.org/wiki/Rational_root_theorem
[n]: https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b
[P_x]: https://wikimedia.org/api/rest_v1/media/math/render/svg/89833156eff2c51bfb8750db3306a0544ce34e14
[r]: https://wikimedia.org/api/rest_v1/media/math/render/svg/0d1ecb613aa2984f0576f70f86650b7c2a132538
[displaystyle _x-r_Q_x]: https://wikimedia.org/api/rest_v1/media/math/render/svg/d86928dcc044a47eb0c6a5156af54a8204be4ec1
[Q_x]: https://wikimedia.org/api/rest_v1/media/math/render/svg/bde0d39b408d6f794d58388248774df9f4d96528
[n-1]: https://wikimedia.org/api/rest_v1/media/math/render/svg/fbd0b0f32b28f51962943ee9ede4fb34198a2521
[s]: https://wikimedia.org/api/rest_v1/media/math/render/svg/01d131dfd7673938b947072a13a9744fe997e632
[displaystyle x-r]: https://wikimedia.org/api/rest_v1/media/math/render/svg/e5886de62c5a5277cb0d9891e41bcd5bb85f880c
[displaystyle x-s]: https://wikimedia.org/api/rest_v1/media/math/render/svg/55e57bdfd22b18c017f3e5f6f9c2700ac37a5083
[x_2_-_r_s_x_rs]: https://wikimedia.org/api/rest_v1/media/math/render/svg/b99be643c17219cc4e6941b46cadadcce8ed4159
[Link 7]: https://zh.wikipedia.org/w/index.php?title=%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%95%BF%E9%99%A4%E6%B3%95&action=edit&section=5
[2]: https://zh.wikipedia.org/wiki/%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%95%BF%E9%99%A4%E6%B3%95#cite_note-2