BZOJ 4652 [Noi2016]循环之美
发布日期:2021-05-04 16:55:24
浏览次数:26
分类:技术文章
本文共 2879 字,大约阅读时间需要 9 分钟。
题目链接
题解
容易发现,若 i j \frac{i}{j} ji在 k k k进制下为纯循环小数,那么必定有
i k l = i m o d    j k l = 1 m o d    j ik^l=i\mod{j}\\ k^l=1\mod{j} ikl=imodjkl=1modj 因此 gcd ( j , k ) = 1 \gcd(j,k)=1 gcd(j,k)=1。那么题目要求的就是
F ( n , m , k ) = ∑ i = 1 n ∑ j = 1 m [ gcd ( i , j ) = 1 ] [ gcd ( j , k ) = 1 ] F(n,m,k)=\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=1][\gcd(j,k)=1] F(n,m,k)=i=1∑nj=1∑m[gcd(i,j)=1][gcd(j,k)=1] 反演得到 F ( n , m , k ) = ∑ d ∣ k F ( m d , n , d ) F(n,m,k)=\sum_{d|k}F(\frac{m}{d},n,d) F(n,m,k)=d∣k∑F(dm,n,d) 边界条件 F ( 0 , m , k ) = F ( n , 0 , k ) = 0 F ( n , m , 1 ) = ∑ i = 1 min ( n , m ) μ ( i ) ⌊ n i ⌋ ⌊ m i ⌋ F(0,m,k)=F(n,0,k)=0\\ F(n,m,1)=\sum_{i=1}^{\min(n,m)}\mu(i)\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor F(0,m,k)=F(n,0,k)=0F(n,m,1)=i=1∑min(n,m)μ(i)⌊in⌋⌊im⌋ 注意需要记忆化。代码
#include
转载地址:https://blog.csdn.net/wang3312362136/article/details/86176834 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月25日 20时03分40秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
用matlab写出信源熵,计算离散信源的熵matlab实现
2019-04-21
php表单yii2,Yii2创建表单(ActiveForm)方法详解
2019-04-21
php 程序授权机制,授权认证详细说明
2019-04-21
java 命令提示符,如何使用Java打开命令提示符并插入命令?
2019-04-21
linux移动文件的脚本,使用Linux脚本移动文件
2019-04-21
linux查看系统所有变量,Linux系统各指标命令
2019-04-21
linux打印机守护程序,linux下怎么编写守护程序呢?
2019-04-21
嵌入式linux 设置时间,time_clock控件应用,使用命令date -s 12:00:00手动设置时间后,时间就停住不走了,我在Ubuntu和嵌入式Linux平台都测试到了...
2019-04-21
linux监控windows,zabbix监控之linux及windows客户端安装配置
2019-04-21
linux中怎么卸载tree,Liunx系统命令中tree命令详解
2019-04-21
linux 网络音箱 混音6,Linux音频编程(三)混音器介绍
2019-04-21
node与mysql开源_node与mysql的相互使用————node+mysql
2019-04-21
mysql连接nginx_nginx四层负载均衡连接mysql
2019-04-21
mysql截取栏目字符_substring从指定字符串开始截取(图)
2019-04-21
python类属性初始化_Python类定义、属性、初始化和析构
2019-04-21