【探究】欧拉反演

大概就是对于 $\varphi$ 函数性质的一点应用?比起 $\mu$ 其实不是那么的复杂,实用性也不是很高。

考虑 $\varphi$ 的这么一个性质:

这大概就是这篇文章的主角。


这东西大概可以用莫比乌斯反演定理来证?

令 $f(x)=\varphi(x)$,$g(x)=\boldsymbol{\rm Id}(x)$ ,则根据狄利克雷卷积的某些常识有

反演一下

当然也可以通过浅显的数论知识来证明:

设 $f(n)=\sum_{d|n}\varphi(d)$ ,则容易证明 $f$ 也是积性函数。(易证=懒得证XD)

考虑 $n$ 的标准分解式:

并且考虑当 $p\in\mathbb{P}$ 时

证明很简单,在不越界的情况下, $p^k$ 由于只有 $p$ 一个质因子,所以与 $p\times1,p\times2\cdots p\times p^{k-1}$ 都不互质,所以是 $p^k-p^{k-1}$ 。

那么有

通过几何级数的求和公式可以得到:

根据积性可以得到

是不是比上一个证明清真了很多!

以下默认 $[i,j]$ 表示 $i,j$ 的 $\rm lcm$ 。

$1$

$1\leq n,m\leq 10^6,q\leq 10^5$

随便做啦


接下来是一道翻车题:

$2$

[国家集训队]Crash的数字表格

$1\leq n,m\leq 10^7$。

根据以往套路变形

看上去很真?但是并不对。原因是 和的倒数不等于倒数的和,也就是中间 $\sum \varphi(d)$ 不能直接提出来。

所以遇到这种情况就只能用莫比乌斯反演。考虑如此:

然后这东西就可以两个数论分块套一起来解决,复杂度 $O(\sqrt n)\cdot O(\sqrt n)=O(n)$。

然而似乎有一只 $\sqrt{n}$ 的做法?有空再学吧233

代码似乎有不少细节?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
bool vis[N] ;
int n, m, pr[N], o ;
LL F[N], mu[N], ans ;

LL do_do(LL u, LL v){
return (u * (u + 1) / 2 % P) * (v * (v + 1) / 2 % P) % P ;
}
LL solve(int x, int y){
LL ret = 0 ;
if (x > y) swap(x, y) ;
// cout << x << " " << y << endl ;
for (int l = 1, r ; l <= x ; l = r + 1){
// cout << l << endl ;
r = min(x / (x / l), y / (y / l)) ;
// if (y == 1) cout << l << " " << r << endl ;
(ret += ((F[r] - F[l - 1]) % P + P) % P * do_do(x / l, y / l) % P) %= P ;
}
return ret ;
}
int main(){
int l, r ;
cin >> n >> m ;
mu[1] = 1 ; if (n > m) swap(n, m) ;
for (int i = 2 ; i <= n ; ++ i){
if (!vis[i])
pr[++ o] = i, mu[i] = -1 ;
for (int j = 1 ; j <= o ; ++ j){
if (pr[j] * i > n) break ;
vis[pr[j] * i] = 1 ;
if (i % pr[j] == 0) {
mu[i * pr[j]] = 0 ; break ;
}
mu[pr[j] * i] = -mu[i] ;
}
}
// cout << 233 << endl ;
for (int i = 1 ; i <= n ; ++ i)
F[i] = ((F[i - 1] + 1ll * i * i * mu[i] % P) % P + P) % P ;
// cout << 233 << endl ;
for (l = 1 ; l <= n ; l = r + 1){
// cout << l << " " << n << endl ;
r = min(n / (n / l), m / (m / l)) ;
// cout << l << " " << r << endl ;
(ans += (1ll * (r - l + 1) * (l + r) / 2 % P) * (solve(n / l, m / l) % P) % P) %= P ;
// cout << l << " " << r << endl ;
}
// cout << 233 << endl ;
cout << ((ans % P + P) % P) << endl ; return 0 ;
}

$3$

LG4917天守阁的地板/LG5221Product

简化题意:

$1\leq n\leq 10^6$

大概就是转化

然后观察到 $\prod$ 对于除法有结合律,即可以分别算分母和分子。同时指数上的 $2$ 也可以最后再算。

于是考虑下半部分:

其中第二步到第三步的原因是根据结合律 $\prod$ 要升级为乘方(就像 $\sum$ 会升级为 $\times $ 一样

发现似乎后面那个是老朋友了,所以可以直接反演成 $\mu$ 形式或者 $\varphi$ 形式。

其中 $\varphi$ 形式的证明大概是考虑每个数的数的贡献,同时由于是有序数对所以是 $\times 2-1$ 。

嗯,然后就会反演成这个样子:

发现后面的可以数论分块于是这就可以 $\sqrt n$ 做了。

对于分子,发现就是:

然后就没有然后了233。

不过 LG5221 卡了空间,于是最后是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
typedef long long LL ;

const int N = 1000001 ;
const int P = 104857601 ;

bool vis[N] ;
int n, pr[80001], cnt ;
int ans1, ans2, phi[N] ;

int expow(int a, int b){
int res = 1 ;
while (b){
if (b & 1)
res = 1ll * res * a % P ;
a = 1ll * a * a % P ; b >>= 1 ;
}
return res ;
}
int main(){
cin >> n ; int fac = 1 ;
pr[0] = phi[1] = 1, ans2 = 1 ;
for (int i = 2 ; i <= n ; ++ i){
if (!vis[i])
pr[++ cnt] = i, phi[i] = i - 1 ;
for (int j = 1 ; j <= cnt ; ++ j){
if (i * pr[j] > n) break ;
vis[i * pr[j]] = 1 ;
if (i % pr[j] == 0) {
phi[i * pr[j]] = phi[i] * pr[j] ;
break ;
}
phi[i * pr[j]] = phi[i] * (pr[j] - 1) ;
}
}
cnt = 0 ;
for (int l = 1, r ; l <= n ; l = r + 1){
r = n / (n / l) ;
pr[++ cnt] = fac ; //cout << l - 1 << " " ;
for (int i = l ; i <= r ; ++ i)
fac = 1ll * fac * i % P ;
pr[++ cnt] = fac ; //cout << r << endl ;
}
// for (int i = 1 ; i <= cnt ; ++ i) cout << pr[i] << endl ;
for (int i = 1 ; i <= n ; ++ i){
phi[i] = phi[i - 1] + phi[i] ;
if (phi[i] > P - 1) phi[i] -= P - 1 ;
}
ans1 = expow(pr[cnt], 2 * n + 2) ; cnt = 0 ;
for (LL l = 1, r ; l <= n ; l = r + 1){
r = n / (n / l) ; int t = ++ cnt ; ++ cnt ;
ans2 = 1ll * ans2 * expow(1ll * pr[cnt] * expow(pr[t], P - 2) % P, phi[n / l]) % P ;
}
printf("%lld\n", 1ll * expow(ans2, P - 5) * ans1 % P) ;
return 0 ;
}