标签 莫比乌斯反演 下的文章
- 首页
- 莫比乌斯反演
洛谷6271 [湖北省队互测2014]一个人的数论
Luogu 分析 先莫比乌斯反演一下 后面那个东西是 $(\mu\cdot \mathbf{id})*\mathbf{id}$，显然是积性函数，所以我们可以对于每个质因子单独计算后乘起来。而对于每个质因子显然只有 $x=1$ 和 $x=p$ 时 $\mu(x)$ 不为 $0$，所以只要算两项即可。 至于 $f_i$，可以求拉格朗日插值公式中每项系数求出，也可以直接高斯消元。 代码 // =...
洛谷3700 [CQOI2017]小Q的表格
Luogu LOJ 分析 可以发现这两条规则长得很像更相减损术，推一推可以得到 最后那一步可以考虑实际意义，证明就不写了（ 如果没有修改的话就可以预处理 $i^2\varphi(i)$ 的前缀和然后数论分块计算了。然而现在还有若干次对于 $f(d,d)$ 的修改，可以想到用一个数据结构来维护。 思考一下，我们在数论分块时需要进行 $\mathcal{O}(Q)$ 次修改和求 $\mathc...
洛谷3312 [SDOI2014]数表
Luogu LOJ 分析 先不考虑 $a$ 的限制，则答案为 这样子可以发现，我们只要把 $\leq a$ 的 $\sigma(k)$ 的贡献设成 $\sigma(k)$、$> a$ 的 $\sigma(k)$ 的贡献设为 $0$ 就可以算出正确答案了。 于是只要把所有询问按 $a$ 排序，然后将 $\sigma(k)$ 从小到大加入即可。 代码 // ===============...
洛谷3704 [SDOI2017]数字表格
Luogu LOJ 分析 下面都假设 $n\leq m$。 方法一 推出来和上面是一样的。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include &...
CF1139D Steps to One
Codeforces Luogu 分析 直接算即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h>...
洛谷6624 [省选联考 2020 A 卷]作业题
Luogu LOJ 分析 显然莫比乌斯反演一下，可以得到 直接做不一定跑得过去，可以加一个剪枝：如果当前满足条件的边数 $<n-1$ 显然当前的 $d$ 的贡献为 $0$，不必再矩阵树计算。这样子复杂度似乎就是对的了。 另外有的高斯消元写法会在生成树个数是 $998244353$ 的倍数的时候 GG，谁能告诉我为啥啊 /kel 代码 // ======================...
洛谷3768 简单的数学题
Luogu 分析 这样就很好杜教筛了。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #defi...
洛谷1587 [NOI2016]循环之美
Luogu LOJ 分析 可以发现，$k$ 进制分数 $\frac{x}{y}$ 是纯循环的当且仅当 $\gcd(y,k)=1$。证明可以点这里。 另外为了避免算重，我们只统计最简分数。 那么我们要求的东西就是（设 $l=\min(n,m)$） 这样子直接枚举约数递归下去算即可；当 $k=1$ 时无法继续往下递归，但此时相当于要求 $\mu(i)$ 的前缀和，杜教筛即可。 代码 // ==...
CF1285F Classical?
Codeforces Luogu 分析 下文中的 $A$ 为 $\max_{i=1}^n\{a_i\}$。 考虑枚举答案的 $\gcd$，问题变为求满足 $\gcd(x,y)=g$ 的 $x,y$ 中 $x\times y$ 的最大值。 可以考虑贪心。我们先把所有满足为 $g$ 的倍数的数拿出来并从大到小排序，然后依次扫描，同时开一个栈来维护。对于每个数，我们需要判断栈中有没有与它互质的数，...