跳至内容
CVBB ACM Team
用户工具
注册
登录
站点工具
搜索
工具
显示页面
修订记录
Copy this page
导出 PDF
反向链接
最近更改
媒体管理器
网站地图
注册
登录
>
最近更改
媒体管理器
网站地图
您在这里:
front_page
»
2020-2021
»
teams
»
intrepidsword
»
2015-beijing-regional
2020-2021:teams:intrepidsword:2015-beijing-regional
本页面只读。您可以查看源文件,但不能更改它。如果您觉得这是系统错误,请联系管理员。
====== 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)$。
2020-2021/teams/intrepidsword/2015-beijing-regional.txt
· 最后更改: 2020/07/17 16:21 由
admin
页面工具
显示页面
修订记录
反向链接
Copy this page
导出 PDF
回到顶部