莫比乌斯

经过本人的研究，发现似乎并没有数学天赋 -o-

$d|n$ 中表示 $d$ 为 $n$ 的约束
快速寻找约束的方法：
直接遍历约束， $\times 1,\times \mathrm{2...}$

切比雪夫定理 ： 对于一个大于 1 的 $k$ , 在 $(k,2k)$ 之间一定存在至少一个质数

莫比乌斯函数

定义域 $N^{\ast }$
$\mu (1)=1$
$\mu (x)=-1$ ， $x$ 为 素数或者为奇数个素数之积
$\mu (x)=1$ ， $x$ 为偶数个素数之积
$\mu (x)=0$ ， $x$ 存在平方因子

性质1

$\mu (a\times b)=\mu (a)\times \mu (b)$ ， 当 $a,b$ 为互质的时候
互质： $gcd(a,b)=1$

莫比乌斯反演

三种应用

计算 $gcd(x,y)=1$ 的个数
计算 $gcd(x,y)=k$ 的个数
计算 $gcd(x,y)$ 的幂

对于应用 1, 2 ：（这里的 $n,m$ 为 $1\le i\le n$ , $1\le j\le m$)

$$cnt=\sum _{d=1}^{min(\frac{n}{k},\frac{m}{k})}\mu (d)\times \lfloor \frac{n}{xd}\rfloor$$

一维计算 $gcd(x,y)=1$ 的个数：$[l,r]$ 与 $n$ 的 $gcd$

$$cnt=\sum _{d|n}\mu (d)(\lfloor \frac{r}{d}\rfloor -\lfloor \frac{l-1}{d}\rfloor )$$

例题：最大公约数图 注意边界！注意边界！注意边界！

vi pr;
vi b(N + 10);
vi f(N + 10, 1);
vi mu(N + 10);
vi dp(N + 2);
 
void prime(){
	rep(i, 1, N) b[i] = i;
	
	f[0] = 0, f[1] = 0;
	mu[1] = 1;
	rep(i, 2, N){
		if(f[i] == 1){
			pr.push_back(i);
			mu[i] = -1;	//素数
		}
		rep(j, 0, pr.size() - 1){
			if(pr[j] * i > N) break;			
			b[pr[j] * i] = i;
			f[pr[j] * i] = 0;
			if(i % pr[j] == 0){
				mu[pr[j] * i] = 0; //含有平方因子
				break;	
			}else{
				mu[pr[j] * i] = -mu[i]; //奇偶翻转
			}
		}
	}
	return;
}
 
void solve(){
	int l, r, n; cin >> l >> r >> n;
 
	if(f[n] == 1){
		cout << r - l + 1 << endl;
		return;
	}
 
	int res = 0;
	int k = lower_bound(pr.begin(), pr.end(), n) - pr.begin() - 1;
	
	if(l <= pr[k]){
	res = (min(pr[k], r) - l + 1) * 2; 
	
	int x = sqrt(n);
	rep(i, 1, x){
		if(n % i) continue;
		int j = n / i;
		res -= mu[i] * ((min(pr[k], r) / i) - (l - 1) / i);
		if(j != i) res -= mu[j] * ((min(pr[k], r) / j) - (l - 1) / j);
	}
	
	}
	per(i, n, pr[k] + 1){
		dp[i] = __gcd(i, n);
		rep(j, i + 1, n - 1){
			dp[i] = min(dp[i], dp[j] + __gcd(i, j));
		}
		if(i <= r && i >= l) res += dp[i];
	}
	rep(i, pr[k] + 1, n) dp[i] = 0; 
	cout << res << endl;
	return;
}
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1;
	cin >> T;
	prime();
	while(T --) solve();
	return 0;
}

三种反演形式

约数反演 - $d$ 是 $n$ 的倍数

若存在 $F(n)={\sum }_{d|n}^{}f(d)$
$f(n)={\sum }_{d|n}^{}\mu (d)F(\frac{n}{d})$

倍数反演 - $n$ 是 $d$ 的倍数

若存在 $F(n)={\sum }_{n|n}^{}f(d)$
$f(n)={\sum }_{n|d}\mu (\frac{d}{n})F(d)$

指数反演 - 略

倍数反演例题

Increment All Divisors

题意
给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,...,A_N)$

你可以对 $A$ 进行以下操作：

• 选择一个 $1\le i\le N$ 的整数 $i$ 。 对于每个作为 $i$ 的正因数（也就是约数）$j$ ， $A_j+=1$

请判断是否可以通过任意次这样的操作使整个序列相等，如果可以请输出最小的操作数，如果不可以输出 -1

$1\le N\le 2\times 10^5$
$1\le A_i\le 10^9$

题解

• 错误思路：
  直接遍历每个数的倍数，如果它的倍数们有比它小的，那么就输出 -1 , 如果都没有，说明一定可以达到，操作数等于 最大数 - 最小数

但是由于最后达到的数不一定是一开始序列的最大数，所以这个思路错误了

• 正确思路：
  $A_i+1$ 的次数为它的倍数被选择的次数加它自己被选择的次数

  记 $x_i$ 为我们选择 $i$ 的次数， 记 $M$ 为最后到达的数（也就是序列元素相等时的每个元素的数）

$$M-A_i=\sum _{i|j}{x}_j$$ $$x_i=\sum _{i|d}\mu (\frac{d}{i})(M-A_d)$$ $$x_i=\sum _{i|d}(\mu (\frac{d}{i})\times M)-(\mu (\frac{d}{i})\times A_d)$$

保证 $x_i$ 一定大于等于 0 , 维护最大下届和最小上界

void prime(){
    rep(i, 1, N - 10) b[i] = i;
 
    f[0] = 0; f[1] = 0;
    mu[1] = 1;
 
    rep(i, 2, N - 10){
        if(f[i] == 1){
            pr.push_back(i);
            mu[i] = -1;
        }
        rep(j, 0, pr.size() - 1){
            if(pr[j] * i > N - 10) break;
            b[pr[j] * i] = i;
            f[pr[j] * i] = 0;
            if(i % pr[j] == 0){
                mu[pr[j] * i] = 0;
                break;
            }else{
                mu[pr[j] * i] = -mu[i];
            }
        }
    }
    return;
}
 
void solve(){
    prime();
    int n; cin >> n;
    
    vi a(n + 1);
    rep(i, 1, n){
        cin >> a[i];
    }
    
    int l = 0, r = INF; //维护最大下届和最小上界, 计算出来的最终 M 的值范围，我们答案需要输出的是操作次数
    rep(i, 1, n){
        int p = 0, q = 0;
        rep(j, 1, n){
            if(i * j > n) break;
            p += mu[j];
            q += mu[j] * a[i * j];
        }
        if(p > 0){
            int x = q / p;
            if(q % p) x ++;
            l = max(l, x);
        }else if(p < 0){
            r = min(r, q / p);
        }else if(q > 0){ // x_i = pM - q, p = 0, x_i >= 0 , -> q <= 0
            cout << -1 << endl;
            return; 
        }
    }
 
    if(l - a[1] < 0 || l > r){
        cout << -1 << endl;
    }else{
        cout << l - a[1] << endl;
    }
    return;
}