拉格朗日插值法

2019-01-23 2019-04-20

Algorithm

3 分钟读完 (大约 497 个字)

给定`n`个点`(x_i,y_i)`来确定一个多项式并将`k`代入求值

对于这个问题我们可以用高斯消元法以`\mathcal{O}(n^3)`的时间复杂度进行求解

但是有一种`\mathcal{O}(n^2)`的方法，名为拉格朗日插值法

$$ f(x)=\sum_{i=1}^{n}y_i\prod_{i \ne j}{\frac{x-x_j}{x_i-x_j}} $$

~~这东西就跟FFT一样烦，DP转移式推着推着发现需要用到拉格朗日插值法~~

数论

「Luogu P1306」斐波那契公约数 - 数论 + 矩阵加速

2019-01-16 2019-01-27

Solution

1 分钟读完 (大约 201 个字)

给定正整数 `n` 和 `m`

求Fibonacci数列第 `n` 项和第 `m` 项的最大公因数

`n,m \le 10^9`

数论, 矩阵加速

2018-12-08 2019-01-27

Solution

3 分钟读完 (大约 421 个字)

给定正整数`n`和`k`

求 `ans = \sum_{i = 1}^n k%i`

要求 `\mathcal{O}(\sqrt{k})` 时间复杂度

数论, 除法分块