莫比乌斯反演简单题

全栈程序员-站长 • 2026年3月18日下午2:10 • 未分类 • 阅读 2

莫比乌斯函数

这里简述一下莫比乌斯函数：

即μ[i]=1表示i是偶数个不同素因子的乘积，μ[i]=-1表示i是奇数个不同素因子的乘积，μ[i]=0表示其他（即如果有相同素因子就是0）

而i==1时，规定μ[1] = 1。

莫比乌斯反演的性质

性质一：（莫比乌斯反演公式）

$f(n) = \sum(d|n) {\mu(d)F(n/d)}$

莫比乌斯反演简单题

性质二：μ(n)是积性函数

性质三：设f是算术函数，它的和函数F(n)=∑(d|n)f(d)是积性函数，那么f也是积性函数。

HDU – 1695 – GCD

题目传送：GCD

题意：求[1,n],[1,m]中gcd为k的两个数的对数

思路：这里可以转化一下，也就是[1,n/k],[1,m/k]之间互质的数的个数，模板题

$F(n) = \sum {(n|d)f(d)}$

所以有：

$f(n) = \sum {(n|d) \mu(d/n)F(d)}$

不过这里需要注意去重，即去掉重复的那一部分的一半即可

$\mathcal AC$ 代码：

#include  #include 
      #include 
      #include 
      #include 
      #include 
      #include 
      #include 
      #include 
      #include 
      #include 
      #include 
      #include 
      #include 
      #include 
      #include 
      #include 
      #include 
      #include 
      #include 
      #include 
      #define LL long long #define INF 0x7fffffff using namespace std; const int maxn = ; bool vis[maxn]; int prime[maxn]; int mu[maxn]; int tot; void init() { memset(vis, 0, sizeof(vis)); mu[1] = 1; tot = 0; for(int i = 2; i < maxn; i ++) { if(!vis[i]) { prime[tot ++] = i; mu[i] = -1; } for(int j = 0; j < tot; j ++) { if(i * prime[j] >= maxn) break; vis[i * prime[j]] = true; if(i % prime[j] == 0) { mu[i * prime[j]] = 0; break; } else { mu[i * prime[j]] = -mu[i]; } } } } int main() { init(); int T; int a, b, c, d, k; scanf("%d", &T); for(int cas = 1; cas <= T; cas ++) { scanf("%d %d %d %d %d", &a, &b, &c, &d, &k); if(k == 0) { printf("Case %d: 0\n", cas); continue; } b /= k; d /= k; if(b > d) swap(b, d); LL ans = 0; for(int i = 1; i <= b; i ++) { ans += (LL)mu[i] * (b / i) * (d / i); } LL t = 0; for(int i = 1; i <= b; i ++) { t += (LL)mu[i] * (b / i) * (b / i); } ans -= t / 2; printf("Case %d: %I64d\n", cas, ans); } return 0; }

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/215331.html原文链接：https://javaforall.net

莫比乌斯反演简单题

莫比乌斯函数

莫比乌斯反演的性质

HDU – 1695 – GCD

关于作者

全栈程序员-站长

发表回复

莫比乌斯反演简单题

莫比乌斯函数

莫比乌斯反演的性质

HDU – 1695 – GCD

关于作者

全栈程序员-站长

相关推荐

java数据库调用「建议收藏」

Smail语法「建议收藏」

列选主元的高斯消去法——MATLAB实现

python求和函数sum()详解

查询数据库隔离级别「建议收藏」

【JAVA定时器】四种常见定时器的原理和简单实现

发表回复