小朋友学Codeforces（5）：Round 453 DIV 2, 902D

一时失言乱红尘 2022-05-31 09:42 111阅读 0赞

# 一、题目 #

[http://codeforces.com/contest/902/problem/D][http_codeforces.com_contest_902_problem_D]

# 二、思路 #

## （一）最大公约数的辗转相除法 ##

对于两个整数a、b，求最大公约数gcd(a,b)的辗转相除法的算法如下

// 辗转相除法 + 递归 
    int gcd(int num1, int num2) 
    {
        if(0 == num2) 
        {
            return num1;
        }
    
        return gcd(num2, num1 % num2);
    }

## （二）题意分析 ##

对于多项式A(x)，定义deg A(x)为多项式的次数。对于多项式A、B，定义多项式mod运算：若A(x)=B(x)·D(x)+R(x),deg R(x)

## （三）本题的思路 ##

辗转相除将多项式对(A,B)转化成(B,A mod B)，最终A mod B为0时，B即为所求。

考虑整数Fibonacci数列：F(0)=1，F(1)=1，F(n+1)=F(n)+F(n-1)。

于是，一次辗转相除法将(F(n+1),F(n))转化成(F(n),F(n-1))。于是，(F(n),F(n-1))在n次辗转相除后结束操作。

类似地，构造多项式的情形：  
P(0) = 1  
P(1) = x  
P(n + 1) = x·P(n) ± P(n-1)

递推时，维护P(n+1)的系数在\{-1,0,1\}中取值，这可以通过符号选择（+/-）实现。

若只取“+”号，还可以进一步构造多项式：  
P(0) = 1  
P(1) = x  
P(n + 1) ≡ \[x·P(n) + P(n-1)\] mod 2 ①  
这里mod 2是为了保证，系数不要超过1。

## （四）例子 ##

例1：根据式子①，求P(0)~p(5)  
P(0) = 1  
P(1) = x  
P(2) = x ^ 2 + 1  
P(3) = \[x ^ 3 + x + x\] mod 2 = x ^ 3  
P(4) = x ^ 4 + x ^ 2 + 1  
P(5) = \[x ^ 5 + x ^ 3 + x + x ^ 3\] mod 2 = x ^ 5 + x

例2：根据P(n + 1) = x·P(n) + P(n-1)，求P(2) / P(1)  
P(2) / P(1)  
= (x ^ 2 + 1) / x  
= x …… 1  
这里的余数1 等于 P(0)

例3：P(n + 1) = x·P(n) + P(n-1)，求P(3) / P(2)  
P(3) / P(2)  
= x ^ 3 / (x ^ 2 + 1)  
= x …… -x  
这里余数-x不完全等于P(1)，差了一个正负号。  
这是因为，用P(2)和P(1)计算P(3)的时候，用了mod 2运算，使得x的系数变为0。  
否则用没取模之前的P(3) = x ^ 3 + 2x去除P(2)，余数正好等于P(1)

# 三、代码 #

#include <iostream>
    using namespace std;
    
    #define MAX_N 200
    int p[MAX_N][MAX_N];
    
    int main()
    {
        // 被除数多项式的次数 
        int deg;
        cin >> deg;
    
        // P(0) = 1, P(x) = x
        p[0][0] = 1;
        p[1][1] = 1;
    
        // p[i + 1] = {x * p[i] + p[i - 1]} % 2;
        // 从第2行一直计算到第n行 
        for (int i = 1; i < deg; i++) 
        {
            // x * p[i] 
            for (int j = 0; j <= i; j++)
            {
                p[i + 1][j + 1] += p[i][j];
            }
    
            // + p[i - 1] 
            for (int j = 0; j <= i - 1; j++)
            {
                p[i + 1][j] += p[i - 1][j];
            }
    
            // % 2 
            for (int j = 0; j <= i + 1; j++)
            {
                p[i + 1][j] %= 2;
            }
    
        }
    
        // 打印被除数多项式的次数 
        cout << deg << "\n";
        // 打印被除数多项式的系数，最常数项系数到最高次系数的顺序 
        for (int i = 0; i <= deg; i++)
        {
            cout << p[deg][i] << " ";
        }
        cout << "\n";
    
        // 打印除数多项式的次数，比被除数多项式的次数少1 
        cout << deg - 1 << "\n";
    
        // 打印除数多项式的系数，按最常数项系数到最高次系数的顺序
        for (int i = 0; i <= deg - 1; i++)
        {
            cout << p[deg - 1][i] << " ";
        }
        cout << "\n";
    
        return 0;
    }

> 更多内容请关注微信公众号  
> ![wechat.jpg][]

[http_codeforces.com_contest_902_problem_D]: http://codeforces.com/contest/902/problem/D
[wechat.jpg]: /images/20220531/d73d3fbbb077461293a1364452e41133.png