这篇文章受密码保护，输入密码才能阅读
题面 以斐波拉契数列为例, 要从矩阵A $$ \begin{bmatrix} f[n-1] & f[n] \end{bmatrix} $$ 得到矩阵B $$ \begin{bmatrix} f[n] & f[n+1] \end{bmatrix} $$ 显然可以$$\begin{bmatrix} f[n-1] & f[n]…
题面 除左下角三个点之外, 可以发现所有能被看到的点$ (x,y)$都满足$ gcd(x,y)=1$. 由于正方形对称性, 我们可以考虑对角线右下方的一半: 所有满足$ 2<=x<y<=N, gcd(x,y)=1$的点, 即对于每个$ 2<=y<=N$, 求$ \varphi (y)$. 答案为$ 3+2*\sum_{…
以下是一些基础性数论结论的简单复习, 和一些代码实现. 证明的坑慢慢补. 内容极其简单基础, 巨佬勿喷... 约数 算术基本定理的推论 设$ N=\prod_{i=1}^{m}P_i^{c_i}$(唯一分解), 则 n的正约数共$$\prod_{i=1}^{m}(c_i+1)$$个. n的所有正约数之和为$$\prod_{i=1}^{m}(\sum…
这篇文章受密码保护，输入密码才能阅读
题面 算数基本定理的推论: 正整数N被唯一分解为$ p_1^{c_1}*p_2^{c_2}*...*p_m^{c_m}$的所有约数的和为$ \prod_{i=1}^{m}(\sum_{j=0}^{c_i}p_i^j)$ (可由N的正约数集合元素之和因式分解得到) 本题求$ A^B$约数和只要把指数乘个B,再用等比数列求和公式. 本题模数为质数, 求…