797. Cyclogenic Polynomials

A monic polynomial is a single-variable polynomial in which the coefficient of highest degree is equal to 1.

Define F to be the set of all monic polynomials with integer coefficients (including the constant polynomial p(x)=1). A polynomial p(x)F is cyclogenic if there exists q(x)F and a positive integer n such that p(x)q(x)=xn1. If n is the smallest such positive integer then p(x) is n-cyclogenic.

Define Pn(x) to be the sum of all n-cyclogenic polynomials. For example, there exist ten 6-cyclogenic polynomials (which divide x61 and no smaller xk1):

x61x4+x3x1x3+2x2+2x+1x2x+1x5+x4+x3+x2+x+1x4x3+x1x32x2+2x1x5x4+x3x2+x1x4+x2+1x3+1

giving

P6(x)=x6+2x5+3x4+5x3+2x2+5x

Also define QN(x)=n=1NPn(x) It's given that Q10(x)=x10+3x9+3x8+7x7+8x6+14x5+11x4+18x3+12x2+23x and Q10(2)=5598.

Find Q107(2). Give your answer modulo 1000000007.

797. 可成圆多项式1

首 1 多项式,是最高次数项的系数为 1 的单变元多项式。

F 为所有整系数首 1 多项式的集合(包括常项式 p(x)=1)。若多项式 p(x)F 满足:存在多项式 q(x)F 与正整数 n 使得 p(x)q(x)=xn1 成立,则称 p(x)可成圆的多项式。如果上述等式里 n 是最小的可使等式成立的正整数,则称 p(x)n-可成圆的多项式。

Pn(x) 为所有 n-可成圆的多项式之和。例如,共有 10 个 6-可成圆的多项式(可整除 x61,不可整除 k 更小的 xk1):

x61x4+x3x1x3+2x2+2x+1x2x+1x5+x4+x3+x2+x+1x4x3+x1x32x2+2x1x5x4+x3x2+x1x4+x2+1x3+1

从而:

P6(x)=x6+2x5+3x4+5x3+2x2+5x

再记:

QN(x)=n=1NPn(x)

已知 Q10(x)=x10+3x9+3x8+7x7+8x6+14x5+11x4+18x3+12x2+23xQ10(2)=5598

Q107(2)1000000007 之值。


这个链接 回到源站。

这个链接 回到详细版题目目录。


1 标题翻译参照数学中的「分圆多项式 / 割圆多项式 (cyclotomic polynomial)」。