Luogu5348 密码解锁
题面
题解
记\(N = \dfrac nm\)
这道题目就是要求\(a_m = \sum_{i=1}^N \mu(i)\mu(im)\)
因为\(\mu(ij) = \mu(i)\mu(j)[\gcd(i, j) = 1]\)
所以\(a_m = \mu(m)\sum_{i=1}^N \mu^2(i) [\gcd(i, m) = 1]\)
设\(\mathbf S(n, m) = \sum_{i=1}^n \mu^2(i)[\gcd(i, m) = 1]\)
则有:
\[
\begin{aligned}
\mathbf S(n, m) &= \sum_{i=1}^n\mu^2(i)\sum_{d|i, d|m}\mu(d) \\
&= \sum_{d|m} \mu(d) \sum_{d|i}^n \mu^2(i) \\
&= \sum_{d|m} \mu(d) \sum_{i=1}^{n/d} \mu^2(id) \\
&= \sum_{d|m} \mu(d) \sum_{i=1}^{n/d} \mu^2(i)\mu^2(d)[\gcd(i, d) = 1] \\
&= \sum_{d|m} \mu^3(d) \sum_{i=1}^{n/d} \mu^2(i)[\gcd(i, d) = 1] \\
&= \sum_{d|m} \mu(d) \mathbf S\left(\left\lfloor\frac nd \right\rfloor, d\right)
\end{aligned}
\]
于是就可以递归处理了。
不过数据太水,\(\mathrm{O}(\sqrt n)\)求\(\mu\)都可以过,上面那个东西不记忆化都可以过,也是毒瘤了。
代码就不放了,太丑了。
最新文章
- Cannot install NodeJs: /usr/bin/env: node: No such file or directory
- (四)C语言柔性数组、指针赋值
- vmware虚拟机挂起后无法再恢复(转)
- 【MVC】 文件及URL 的整理
- 生成XML文件,通过实体生成XML文件
- freebsd安装和图形界面安装
- Mac OS升级到Yosemite后一些问题
- 利用HTML5的devicemotion事件实现手机摇一摇抽奖,年会抽奖
- jQuery开发自定义插件 $.extend()与$.fn.extend()
- Kubernetes存储之Persistent Volumes简介
- hdu5444(模拟)
- [LeetCode] Prime Palindrome 质数回文数
- HTTP Basic和Digest认证介绍与计算
- sort_gff.py
- session cookie简介
- strcmp,stricmp
- 上任com的发布流程
- java工程师基础笔试题(一)
- input标签type=button时,如何禁用和开启按钮
- CF980E The Number Games【树链剖分/线段树】