加载中...

因数、gcd等式子用莫比乌斯函数表示的一种简单方法

发表于2023-08-18|OI（高中）2023-2024赛季

|总字数:284|阅读时长:1分钟|浏览量:

因数、gcd等式子用莫比乌斯函数表示的一种简单方法

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132355546

在这里插入图片描述

对于此式，可以发现，本质就是把T的质因子集合全部抽出来，划分成两个不交的集合。假设 $T$ 的集合大小为 $w(T)$ ，那么这个式子本质上就是 $2^{w(T)}$

现在考虑用积性函数的形式表示，我们对 $d$ 进行唯一素数表示，发现对于 $d_1, d_2$ ，若他们的底数种类相同，指数不一样，他们是在同一个等价类里面的。

所以我们只需要考虑所有指数都为 $1$ 的 $d$ ，也就是 不含平方因子 的 $d$ ，发现这可以是个莫比乌斯函数的形式。但我们发现莫比乌斯函数有±1的情况，所以我们取个平方即可。

最终可以表示成：
在这里插入图片描述

之后就可以套杜教了

化简只需要：

在这里插入图片描述

下次总结

文章作者: zhangxixi

文章链接: http://zhangxixi2008.github.io/post/e5572a04

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！

相关推荐

【Loj #10012. 「一本通 1.2 例 2」Best Cow Fences】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15669626.html 题目链接题目给定一个长度为 nnn 的非负整数序列 AAA ，求一个平均数最大的，长度不小于 LLL 的子段。思路先二分平均值。然后是判断。如何判断一段数中是否存在长度大于等于 LLL 且平均值大于某个数的子段呢？我们可以先让序列中的数都减去二分中的值，然后就转化为：序列中是否存在长度大于等于 LLL 的字段和为正。我们可以先构造一个前缀和。假设我们当前算到序列中的第 iii 项，我们只需要在前 i−...

对于模拟最大流的一些猜测

对于模拟最大流的一些猜测本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132093553 先把最大流转成最小割。然后对最小割分类讨论，观察性质，看看有什么不用跑最大流的做法？等我长大再回来想。

对于DP颜色类问题的切换方法：P9561

对于dp颜色类问题的切换方法：P9561 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132471731 对于dp颜色类问题的切换方法两种颜色为例，一般情况下 dp[i][0]dp[i][0]dp[i][0] 可以由 dp[j][0/1]dp[j][0/1]dp[j][0/1] 在某些情况下转移但从0到0的过程中，对于 jjj 前的1，可能 jjj 满足，但 iii 不满足此时可以考虑0只从1转移，1只从0转移，对于新的0，我们除了统计当前dp值，我...

【一本通OJ 1600：【例 4】旅行问题】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15901652.html 题目链接题目原题来自：POI 2004 John 打算驾驶一辆汽车周游一个环形公路。公路上总共有 nnn 车站，每站都有若干升汽油（有的站可能油量为零），每升油可以让汽车行驶一千米。John 必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。在一开始的时候，汽车内油量为零，John 每到一个车站就把该站所有的油都带上（起点站亦是如此），行驶过程中不能出现没有油的情况。任务：判断以每个车站为...

【P2344 [USACO11FEB]Generic Cow Protests G】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15574309.html 题目链接首先朴素dp不用讲，设 dpidp_idpi 表示前 iii 个数划分的总方案数，SiS_iSi 表示前 iii 个数的和。 dpi=∑j=0i−1dpj (Si−Sj⩾0)dp_i=\sum_{j=0}^{i-1}dp_j\,\,\,(S_i-S_j\geqslant 0) dpi=j=0∑i−1dpj(Si−Sj⩾0) 其中 dp0=1dp_0=1dp0=1。可是这样的时间复杂度为 O...

【CF1304C Air Conditioner】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15826957.html 题目 Gildong owns a bulgogi restaurant. The restaurant has a lot of customers, so many of them like to make a reservation before visiting it. Gildong tries so hard to satisfy the customers that he even memorized al...

数据加载中