一、题目

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; }

更多内容请关注微信公众号