积性函数、莫比乌斯反演

大家好，欢迎来到IT知识分享网。

力扣 2338. 统计理想数组的数目（积性函数）

HYSBZ 2301 Problem b（莫比乌斯反演）

HYSBZ 2440 完全平方数（莫比乌斯反演）

一，积性函数

1，积性、完全积性

积性函数指对于所有互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数。

完全积性函数指对于所有的整数a和b有性质f(ab)=f(a)f(b)的数论函数。

2，性质

若f可积，则 $f(p_1^{a_1}p_2^{a_2}...p_k^{a_k})=f(p_1^{a_1})f(p_2^{a_2})......f(p_k^{a_k})$

若f可积，则 $g(n)=\sum_{d|n}f(d)$ 可积， $F(n)=\sum_{d|n}f(d)g(\frac{n}{d})$ 可积

二，莫比乌斯函数

1，莫比乌斯函数 μ

①μ(1)=1

②μ(p₁p₂……pₐ)=(-1)^a，其中a个p为不同素数。

③其余情况μ(d)=0

即，有素因子的平方的，函数值为0，没有平方的话，函数值为-1的素因子个数次方。

2，性质

μ 是积性函数

当n>1时， $\sum_{d|n}\mu(d)=0$

三，莫比乌斯反演

1，莫比乌斯反演

若 $g(n)=\sum_{d|n}f(d)$ ，则 $f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})$

反之，若 $f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})$ ，则 $g(n)=\sum_{d|n}f(d)$

2，性质

（1）设f是数论函数，它的和函数 $\sum_{d|n}f(d)$ 是积性函数，那么f也是积性函数。

（2）若函数f满足f(1)=1，当n>1时， $\sum_{d|n}f(d)=0$ ，则f是积性函数，进一步可推出f就是μ

3，欧拉函数的反演

$\sum_{d|n}\varphi (d)=n$ ，故 $\varphi(n)=n\sum_{d|n}\frac{\mu(d)}{d}$

四，莫比乌斯反演二

五，OJ实战

POJ 1091 跳蚤（积性函数）

Description

Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。
比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。
当确定N和M后，显然一共有M^N张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。
Input

我看很多人都是用容斥原理，直接求出答案。也有很多人用容斥原理推出表达式，然后计算这个表达式。

我觉得用容斥原理还是一个不错的思路的，不过我是用别的方法做的，得到的表达式是一样的。

枚举所有数的gcd，可以得到m^n=∑(f(d,n)) for all d that d|m

其中f就是表示本题需要求的东西。

根据积性函数的特性，只需要求出f(p^k,n)即可求出f(m,n)

f(p^k,n)=p^(k*n)*(1-1/p^n) (这个地方要注意运算顺序，不能把1/p^n直接弄成0了)

设m的不同的素因子分别为p1,p2,p3……pl

那么，f(m,n)=m^n*(1-1/p1^n)(1-1/p2^n)(1-1/p3^n)……(1-1/pl^n)

import java.util.*; import java.math.BigInteger; public class Main { public static void f(int m, int n) { BigInteger s=new BigInteger("1"); for (int p = 2; p*p <= m; p++) { if (m%p == 0) { BigInteger pn =new BigInteger("1"); for (int j = 1; j <= n; j++) pn=pn.multiply(BigInteger.valueOf(p)); BigInteger pnk =new BigInteger("1"); while (m%p == 0) { m /= p; pnk=pnk.multiply(pn); } BigInteger pnk1=new BigInteger("0"); pnk1=pnk1.add(pnk); s=s.multiply(pnk1.subtract(pnk.divide(pn))); } } if (m > 1) { BigInteger pn =new BigInteger("1"); for (int j = 1; j <= n; j++)pn=pn.multiply(BigInteger.valueOf(m)); s=s.multiply(pn.subtract(BigInteger.valueOf(1))); } System.out.println(s.toString()); } public static void main(String[] args) { Scanner cin = new Scanner(System.in); int n=Integer.parseInt(cin.next()); int m=Integer.parseInt(cin.next()); f(m,n); } }

力扣 2338. 统计理想数组的数目（积性函数）

给你两个整数 n 和 maxValue ，用于描述一个 理想数组 。

对于下标从 0 开始、长度为 n 的整数数组 arr ，如果满足以下条件，则认为该数组是一个 理想数组 ：

每个 arr[i] 都是从 1 到 maxValue 范围内的一个值，其中 0 <= i < n 。
每个 arr[i] 都可以被 arr[i - 1] 整除，其中 0 < i < n 。

返回长度为 n 的不同理想数组的数目。由于答案可能很大，返回对 109 + 7 取余的结果。

示例 1：

输入：n = 2, maxValue = 5 输出：10 解释：存在以下理想数组： - 以 1 开头的数组（5 个）：[1,1]、[1,2]、[1,3]、[1,4]、[1,5] - 以 2 开头的数组（2 个）：[2,2]、[2,4] - 以 3 开头的数组（1 个）：[3,3] - 以 4 开头的数组（1 个）：[4,4] - 以 5 开头的数组（1 个）：[5,5] 共计 5 + 2 + 1 + 1 + 1 = 10 个不同理想数组。

示例 2：

输入：n = 5, maxValue = 3 输出：11 解释：存在以下理想数组： - 以 1 开头的数组（9 个）： - 不含其他不同值（1 个）：[1,1,1,1,1] - 含一个不同值 2（4 个）：[1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2] - 含一个不同值 3（4 个）：[1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3] - 以 2 开头的数组（1 个）：[2,2,2,2,2] - 以 3 开头的数组（1 个）：[3,3,3,3,3] 共计 9 + 1 + 1 = 11 个不同理想数组。

提示：

2 <= n <= 104
1 <= maxValue <= 104

思路一：

用dp备忘录实现递推式。

代码：

class Solution { public: int dp(int n, int maxValue) { if (n == 1)return 1; if (!m[n][maxValue])for (auto x : mdiv[maxValue])m[n][maxValue] += dp(n - 1, x), m[n][maxValue] %= p; return m[n][maxValue]; } int idealArrays(int n, int maxValue) { for (int i = 1; i <= maxValue; i++)mdiv[i] = GetDivisors(i); int ans = 0; for (int i = 1; i <= maxValue; i++)ans = (ans + dp(n, i)) % p; return ans; } map<int, vector<int>>mdiv; map<int, map<int, int>>m; int p = ; };

idealArrays即f，dp即g

调用Solution().idealArrays(5878,2900)耗时50秒！！！

思路二：思路一 + 只优化g函数

因为g函数是积性函数，所以可以优化g的递推式。

思路可行但是比较复杂，不展开了。

思路三：思路一 + 新的递推式

因为g函数是积性函数，所以我们可以把整个递推式优化成：

其中m1…mk都是单素数幂，他们两两互质，乘积为m

代码：

class Solution { public: int dp(int n, int maxValue) { if (n == 1)return 1; if (!m[n][maxValue])for (auto x : mdiv[maxValue])m[n][maxValue] += dp(n - 1, x), m[n][maxValue] %= p; return m[n][maxValue]; } int idealArrays(int n, int maxValue) { for (int i = 1; i <= maxValue; i++)mdiv[i] = GetDivisors(i); int ans = 0; for (int i = 1; i <= maxValue; i++) { auto v = Fenjie2(i); long long s = 1; for (auto vi : v)s = s * dp(n, vi) % p; ans = (ans + s) % p; } return ans; } map<int, vector<int>>mdiv; map<int, map<int, int>>m; int p = ; };

idealArrays即f，dp即h

调用Solution().idealArrays(5878,2900)耗时2331毫秒

思路四：思路三 + 只优化h函数

我们把h函数的定义域缩小为m仅限单素数幂：（这一步只是逻辑转化，没有运算层面的改变）

于是，可以进一步简化：（这一步简化降低了时间复杂度）

于是，还可以进一步简化：（这一步简化又降低了时间复杂度）

class Solution { public: int dp(int n, int a) { if (n == 1)return 1; if (a == 0)return 1; if (!m[n][a])m[n][a] = (dp(n - 1, a) + dp(n, a - 1)) % pp; return m[n][a]; } int idealArrays(int n, int maxValue) { int ans = 0; for (int i = 1; i <= maxValue; i++) { auto v = Fenjie(i); long long s = 1; for (auto vi : v)s = s * dp(n, vi.second) % pp; ans = (ans + s) % pp; } return ans; } map<int, map<int, int>>m; int pp = ; };

调用Solution().idealArrays(5878,2900)耗时31毫秒

思路五：

其实h就是组合数。

HYSBZ 2301 Problem b（莫比乌斯反演）

题目：

Sample Input
2
2 5 1 5 1
1 5 1 5 2
Sample Output

思路：

首先把问题化简成，求有多少个数对(x,y)满足1<=x<=n,1<=y<=m且gcd(x,y)=1

这里我们只需要求f(1)即可

优化的关键是快速枚举除法取值，太厉害了

代码：

#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; const int N = 50000; bool prime[N]; int u[N], su[N];//su是u的前缀和 void getu() { for (int i = 0; i < N; i++)prime[i] = true, u[i] = 1; prime[1] = false; for (int i = 2; i < N; i++)if (prime[i])for (int j = 1; i* j < N; j++) prime[i*j] = false, u[i*j] *= -1 * (j%i != 0); su[0] = u[0]; for (int i = 1; i < N; i++)su[i] = su[i - 1] + u[i]; } int f(int n, int m)//有多少个数对(x,y)满足1<=x<=n,1<=y<=m且gcd(x,y)=1 { int res = 0; for (int i = 1, key; i <= n && i <= m; i = key + 1) { key = min(n / (n / i), m / (m / i)); res += (n / i)*(m / i)*(su[key] - su[i - 1]); } return res; } int main() { int n, a, b, c, d, k; scanf("%d", &n); getu(); while (n--) { scanf("%d%d%d%d%d", &a, &b, &c, &d, &k); a--, c--; a /= k, b /= k, c /= k, d /= k; printf("%d\n", f(b, d) - f(a, d) - f(b, c) + f(a, c)); } return 0; }

HYSBZ 2440 完全平方数（莫比乌斯反演）

题目：

小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些
数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而
这丝毫不影响他对其他数的热爱。
这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一
个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了
小X。小X很开心地收下了。
然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗？

Input
包含多组测试数据。文件第一行有一个整数 T，表示测试
数据的组数。
第2 至第T+1 行每行有一个整数Ki，描述一组数据，含义如题目中所描述。

Output
含T 行，分别对每组数据作出回答。第 i 行输出相应的
第Ki 个不是完全平方数的正整数倍的数。

Sample Input
4
1
13
100

Sample Output

1
19
163

首先算出莫比乌斯函数前面若干项，

然后有个函数f计算前n个数有多少个不是完全平方数的倍数，

最后根据这个函数来二分，查找满足f(n)=k的最小n

因为一开始的满足f(n)=k的最小n肯定小于2k，所以n的范围是2*10^9，那么莫比乌斯函数算出前50000个即可，

这个估算是必不可少的，因为题目没说答案一定在int的范围内。

至于为什么满足f(n)=k的最小n肯定小于2k，这个可以计算

因为f(n)/n=(1-1/2/2)*(1-1/3/3)*(1-1/5/5)…… >0.5

所以f(n)>0.5n

代码：

#include<iostream> using namespace std; const int N = 50000; bool prime[N]; int u[N]; void getu() { for (int i = 0; i < N; i++)prime[i] = true, u[i] = 1; prime[1] = false; for (int i = 2; i < N; i++)if (prime[i])for (int j = 1; i* j < N; j++) prime[i*j] = false, u[i*j] *= -1 * (j%i != 0); } int f(int n)//前n个数有多少个不是完全平方数的倍数 { int r = 0; for (int i = 1; i*i <= n; i++)r += u[i] * n / i / i; return r; } int main() { getu(); int t, k; cin >> t; while (t--) { cin >> k; int low = 1, high = k * 2; //二分查找满足f(n)=k的最小n while (low < high) { int mid = (high - low) / 2 + low; if (f(mid) < k)low = mid + 1; else high = mid; } cout << low << endl; } return 0; }

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/156751.html

积性函数、莫比乌斯反演

一，积性函数

1，积性、完全积性

2，性质

二，莫比乌斯函数

1，莫比乌斯函数 μ

2，性质

三，莫比乌斯反演

1，莫比乌斯反演

2，性质

3，欧拉函数的反演

四，莫比乌斯反演二

五，OJ实战

POJ 1091 跳蚤（积性函数）

力扣 2338. 统计理想数组的数目（积性函数）

HYSBZ 2301 Problem b（莫比乌斯反演）

HYSBZ 2440 完全平方数（莫比乌斯反演）

相关推荐

发表回复