Warning: session_start(): open(/tmp/sess_75f5fb5f14d6e349f2a1a387a0c3b266, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/4/43994124a9168f34c03db2ff7cd35d94.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== Contest Info ======
date: 2020.07.16 13:00-18:00
[[https://vjudge.net/contest/383596|practice link]]
====== 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)$。