2020-2021:teams:intrepidsword:2015-beijing-regional
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:intrepidsword:2015-beijing-regional [2020/07/17 15:52] admin 创建 |
2020-2021:teams:intrepidsword:2015-beijing-regional [2020/07/17 16:21] (当前版本) admin add K |
||
|---|---|---|---|
| 行 6: | 行 6: | ||
| ====== Solutions ====== | ====== Solutions ====== | ||
| + | |||
| + | ===== K. A Math Problem ===== | ||
| + | |||
| + | **题目大意**：定义一个 $\mathbb{N}^{+}\to\mathbb{N}^{+}$ 的数论函数 $f$，满足 $f(1)=1$，$3f(n)f(2n + 1)=f(2n)(1 + 3f(n))$，$f(2n)<6f(n)$。给定 $n$ 和一个质数 $p$，对于每个 $i\in[0,p)$，求 $f(1)\sim f(n)$ 中有多少个模 $p$ 余 $i$。 | ||
| + | |||
| + | **题解**：$f(2n+1)=f(2n)\frac{1+3f(n)}{3f(n)}$。由于 $1+3f(n)$ 和 $3f(n)$ 互质，因此 $f(2n)$ 必须被 $3f(n)$ 整除。故 $f(2n)=3f(n)$。这样用一个简单的数位 dp 即可解决。 | ||
| + | |||
| + | 时间复杂度 $\mathcal{O}(p\log n)$。 | ||
| + | |||
2020-2021/teams/intrepidsword/2015-beijing-regional.1594972341.txt.gz · 最后更改: 2020/07/17 15:52 由 admin
