Project Euler 太好玩了。。。（雾

Problem 675

设 \(\omega(n)\) 表示 \(n\) 的质因子个数，\(S(n)=\sum_{d|n}2^{\omega(d)}\)，求 \(F(n)=\sum_{i=2}^nS(i!) \bmod (10^9+87)\)。

\(n=10^7\)

solution

\(n=\prod_{i=1}^kp_i^{e_i}\)
\(S(n)=\prod_{i=1}^k(2e_i+1)\)
线性筛求出每个数的最小质因子之后就可以对 \(10^7\) 以内的所有数质因数分解了。
时间复杂度 \(O(\sum_{i=1}^n\omega(i))\)

Problem 225

Tribonacci Number:\(T_1=T_2=T_3=1\)，\(T_n=T_{n-1}+T_{n-2}+T_{n-3}\)。

求第 124 小的奇数 \(k\) 满足对任意正整数 \(n\)，\(k\not|T_n\)。

solution

答案很小，暴力即可。

Problem 137

设 Fibonacci 的生成函数为 \(A_F(x)\)，若 \(x\in \Q_+\) 且 \(A_F(x)\in \N_+\)，则称 \(A_F(x)\) 为 Fibonacci golden nuggets。求第 15 小的这样的数。
\[ \begin{aligned}A_F(x)&=\frac{x}{1-x-x^2} \\&=\frac{\frac{c}{d}}{1-\frac{c}{d}-\frac{c^2}{d^2}} \\&=\frac{cd}{c^2-cd+d^2}\end{aligned} \]
若 \((c,d)=1\)，因为 \((cd,c^2-cd+d^2)=(c,c^2-cd+d^2)(d,c^2-cd+d^2)=(c,d^2)(d,c^2)=1\)，所以 \(c^2-cd+d^2=1\)。

结论：\(x=\frac{F_{2n+1}}{F_{2n}}\)时 \(n=F_{2n+1}F_{2n}\)，其中 \(F_n\) 是 Fibonacci 数。

证明咕了。。