Project Euler 479

题目

Roots on the Rise

Let $a_k$, $b_k$, and $c_k$ represent the three solutions (real or complex numbers) to the equation

$\dfrac{1}{x}=\left(\dfrac{k}{x}\right)^2(k+x^2)-kx$.

For instance, for $k=5$, we see that ${a_5, b_5, c_5 }$ is approximately ${5.727244, -0.363622+2.057397i, -0.363622-2.057397i}$.

Let $\displaystyle S(n) = \sum{p=1}^n\sum{k=1}^n(a_k+b_k)^p(b_k+c_k)^p(c_k+a_k)^p$.

Interestingly, $S(n)$ is always an integer. For example, $S(4) = 51160$.

Find $S(10^6) \text{ modulo }1\,000\,000\,007$.

解决方案

经过去分母和移项，原方程转化为$kx^3-k^2x^2+x-k^3=0(x \neq 0)$。

根据该页面关于三元一次方程$ax^3+bx^2+cx+d=0$的韦达定理：

$$x_1+x_2+x_3=-\dfrac{b}{a},x_1x_2+x_2x_3+x_1x_3=\dfrac{c}{a},x_1x_2x_3=-\dfrac{d}{a}$$

得到：

$$a_k+b_k+c_k=k,a_kb_k+b_kc_k+c_ka_k=\dfrac{1}{k},a_kb_kc_k=k^2$$

那么

$$(a_k+b_k)(b_k+c_k)(a_k+c_k)=(a_k+b_k+c_k)(a_kb_k+b_kc_k+c_ka_k)-a_kb_kc_k=1-k^2$$

因此再根据等比数列求和公式，有

$$S(n)=\sum_{k=1}^n\sum_{p=1}^n(1-k^2)^p=-\sum_{k=1}^n\dfrac{(1-k^2)((1-k^2)^n-1)}{k^2}$$

代码

N = 10**6
mod = 10 ** 9 + 7

ans = 0
for k in range(2, N + 1):
    ans = (ans - (1 - k * k) * (pow(1 - k * k, N, mod) - 1) % mod * pow(k * k, mod - 2, mod)) % mod
print(ans)