当前位置:网站首页>Mobius inversion
Mobius inversion
2022-04-23 09:42:00 【Zimba_】
Preface :
Just finished writing the product function , Two more today , More sleep .
Mobius function μ ( n ) \mu(n) μ(n):
I don't know where Dirichlet's go Next door attend class;class begins .
How to find Mobius function is also mentioned next door .
And we know u ∗ 1 = e u*1=e u∗1=e.
Now let's learn how to use Mobius function .
you 're right , That's Mobius inversion .
Mobius inversion :
What is Mobius inversion ?
We set up f f f Is a number theoretic function , f f f The value of the sum function of is F ( n ) = ∑ d ∣ n f ( d ) F(n)=\sum_{d|n}f(d) F(n)=∑d∣nf(d), Its value is determined by f f f Decisive .
Now we're going to reverse this relationship , Let's get used to F F F To solve f f f The way to .
This is Mobius inversion .
We found that the original formula is actually F = 1 ∗ f F=1*f F=1∗f, Ride on both sides μ \mu μ, Got it. f = μ ∗ F f=\mu *F f=μ∗F.
In fact, this is a formula of Mobius inversion .
Of course , The more specific formula is long like this ,
It is known that F ( n ) = ∑ d ∣ n f ( d ) F(n)=\sum_{d|n}f(d) F(n)=∑d∣nf(d), Then there are f ( n ) = ∑ d ∣ n μ ( d ) F ( n / d ) f(n)=\sum_{d|n}\mu(d)F(n/d) f(n)=∑d∣nμ(d)F(n/d)( perhaps ∑ d ∣ n μ ( n / d ) F ( n ) \sum_{d|n}\mu(n/d)F(n) ∑d∣nμ(n/d)F(n)).
Then there is the second formula ,
It is known that F ( n ) = ∑ n ∣ d f ( d ) F(n)=\sum_{n|d}f(d) F(n)=∑n∣df(d), Then there are f ( n ) = ∑ n ∣ d μ ( d / n ) F ( d ) f(n)=\sum_{n|d}\mu(d/n)F(d) f(n)=∑n∣dμ(d/n)F(d).( This proof is slightly )
in other words , When we ask for f ( n ) f(n) f(n), however f ( n ) f(n) f(n) It's not easy to ask , however F ( n ) F(n) F(n) But unexpectedly good beg . that , After we learn Mobius inversion , You can go through this F ( n ) F(n) F(n), To get f ( n ) f(n) f(n) The value of the .
That's how it works , This thing still needs more questions to figure out .
application :
problem 1:
Give two intervals [ a , b ] [a,b] [a,b] and [ c , d ] [c,d] [c,d], How many reciprocal prime pairs of integers x x x and y y y Satisfy a ⩽ x ⩽ b a\leqslant x\leqslant b a⩽x⩽b And c ⩽ y ⩽ d c\leqslant y\leqslant d c⩽y⩽d. ( 1 ⩽ a ⩽ b ⩽ 1 e 7 , 1 ⩽ c ⩽ d ⩽ 1 e 7 ) (1\leqslant a\leqslant b\leqslant 1e7,1\leqslant c\leqslant d\leqslant 1e7) (1⩽a⩽b⩽1e7,1⩽c⩽d⩽1e7)
Explain :
There are two ways .
Let's start with the serious Mobius inversion .
We make f ( t ) f(t) f(t) Express satisfaction t = g c d ( x , y ) t=gcd(x,y) t=gcd(x,y), And a ⩽ x ⩽ b , c ⩽ y ⩽ d a\leqslant x\leqslant b,c\leqslant y\leqslant d a⩽x⩽b,c⩽y⩽d The logarithmic .
Then make F ( t ) F(t) F(t) Express satisfaction t ∣ g c d ( x , y ) t|gcd(x,y) t∣gcd(x,y), And a ⩽ x ⩽ b , c ⩽ y ⩽ d a\leqslant x\leqslant b,c\leqslant y\leqslant d a⩽x⩽b,c⩽y⩽d The logarithmic .
Will find F ( t ) F(t) F(t) You can ask directly , t ∣ g c d ( x , y ) t|gcd(x,y) t∣gcd(x,y) That is to say t ∣ x t|x t∣x And t ∣ y t|y t∣y, That's how many x x x By d d d to be divisible by , How many y y y By d d d to be divisible by , Multiply it again . obtain F ( t ) = ( ⌊ b t ⌋ − ⌈ a t ⌉ + 1 ) ( ⌊ d t ⌋ − ⌈ c t ⌉ + 1 ) F(t)=(\left \lfloor \frac{b}{t}\right \rfloor-\left \lceil \frac{a}{t}\right \rceil+1)(\left \lfloor \frac{d}{t}\right \rfloor-\left \lceil \frac{c}{t}\right \rceil+1) F(t)=(⌊tb⌋−⌈ta⌉+1)(⌊td⌋−⌈tc⌉+1)
And there are F ( n ) = ∑ n ∣ t f ( t ) F(n)=\sum_{n|t}f(t) F(n)=∑n∣tf(t),
After inversion, it becomes f ( n ) = ∑ n ∣ t μ ( t / n ) F ( t ) f(n)=\sum_{n|t}\mu(t/n)F(t) f(n)=∑n∣tμ(t/n)F(t).
So what we ask f ( 1 ) = ∑ 1 ∣ t μ ( t ) F ( t ) . f(1)=\sum_{1|t}\mu(t)F(t). f(1)=∑1∣tμ(t)F(t).
The next step is to enumerate t t t, The upper limit is m i n ( b , d ) min(b,d) min(b,d).
Say another thing .
Look at the expression [ g c d ( x , y ) = 1 ] [gcd(x,y)=1] [gcd(x,y)=1].
This reminds us of the unit function e ( n ) = [ n = 1 ] e(n)=[n=1] e(n)=[n=1].
then e = μ ∗ 1 e=\mu *1 e=μ∗1, You can get an important expression ∑ d ∣ n μ ( d ) = [ n = 1 ] \sum_{d|n}\mu(d)=[n=1] ∑d∣nμ(d)=[n=1].
Then we start to push the formula ,
∑ x = a b ∑ y = c d [ g c d ( x , y ) = 1 ] \sum_{x=a}^{b}\sum_{y=c}^{d}[gcd(x,y)=1] ∑x=ab∑y=cd[gcd(x,y)=1]
= ∑ x = a b ∑ y = c d ∑ t ∣ g c d ( x , y ) μ ( t ) =\sum_{x=a}^{b}\sum_{y=c}^{d}\sum_{t|gcd(x,y)}\mu(t) =∑x=ab∑y=cd∑t∣gcd(x,y)μ(t)
= ∑ x = a b ∑ y = c d ∑ t ∣ x , t ∣ y μ ( t ) =\sum_{x=a}^{b}\sum_{y=c}^{d}\sum_{t|x,t|y}\mu(t) =∑x=ab∑y=cd∑t∣x,t∣yμ(t)
= ∑ t = 1 m i n ( b , d ) μ ( t ) ∑ x = a b [ t ∣ x ] ∑ y = c d [ t ∣ y ] =\sum_{t=1}^{min(b,d)}\mu(t)\sum_{x=a}^{b}[t|x]\sum_{y=c}^{d}[t|y] =∑t=1min(b,d)μ(t)∑x=ab[t∣x]∑y=cd[t∣y]
= ∑ t = 1 m i n ( b , d ) μ ( t ) ( ⌊ b t ⌋ − ⌈ a t ⌉ + 1 ) ( ⌊ d t ⌋ − ⌈ c t ⌉ + 1 ) =\sum_{t=1}^{min(b,d)}\mu(t)(\left \lfloor \frac{b}{t}\right \rfloor-\left \lceil \frac{a}{t}\right \rceil+1)(\left \lfloor \frac{d}{t}\right \rfloor-\left \lceil \frac{c}{t}\right \rceil+1) =∑t=1min(b,d)μ(t)(⌊tb⌋−⌈ta⌉+1)(⌊td⌋−⌈tc⌉+1)
Then it's all right .
It's easy to get started , notice [ g c d ( x , y ) = 1 ] [gcd(x,y)=1] [gcd(x,y)=1] Just put it in , And then put g c d gcd gcd Mentioned earlier to enumerate , If it is [ g c d ( x , y ) = k ] [gcd(x,y)=k] [gcd(x,y)=k], It turns into 1 1 1 The situation of .
But it is necessary to study inversion carefully .
With integral division , It can also be optimized to 1 e 7 \sqrt{1e7} 1e7, But the preprocessing Mobius here has run so much , So don't do it .
Code up :
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
typedef pair<int,int> P;
const ll MAXN=10000010;
ll prime[MAXN+10],notPrime[MAXN+10],mu[MAXN+10],tot;
void initMu(int n)
{
notPrime[1]=mu[1]=1;
for(int i=2;i<=n;i++)
{
if(!notPrime[i])prime[tot++]=i,mu[i]=-1;
for(int j=0;j<tot&&i*prime[j]<=n;j++)
{
notPrime[i*prime[j]]=1;
if(i%prime[j])mu[i*prime[j]]=-mu[i];
else {
mu[i*prime[j]]=0;break;}
}
}
}
int main()
{
initMu(MAXN);
ll a,b,c,d;
cin>>a>>b>>c>>d;
ll ans=0;
for(ll i=1;i<=max(b,d);i++)
{
ans+=mu[i]*(b/i-(a+i-1)/i+1)*(d/i-(c+i-1)/i+1);
}
cout<<ans<<endl;
return 0;
}
problem 2:
This problem , For discussion φ = μ ∗ i d \varphi=\mu*id φ=μ∗id This formula .
Explain :
According to this formula , Let's backhand a mobius inversion to find the Euler function .( Although not actually , This formula will work, but it will work )
It seems to be a simplified version of the previous question ..
Is to find the interval [ 1 , n ] [1,n] [1,n] and [ n , n ] [n,n] [n,n] Logarithm of Coprime in two intervals .
So we'll follow the derivation of the previous question , We get the formula ,
φ ( n ) = ∑ t = 1 n μ ( t ) ( ⌊ n t ⌋ − ⌈ n t ⌉ + 1 ) ( ⌊ n t ⌋ − ⌈ 1 t ⌉ + 1 ) \varphi(n)=\sum_{t=1}^{n}\mu(t)(\left \lfloor \frac{n}{t}\right \rfloor-\left \lceil \frac{n}{t}\right \rceil+1)(\left \lfloor \frac{n}{t}\right \rfloor-\left \lceil \frac{1}{t}\right \rceil+1) φ(n)=∑t=1nμ(t)(⌊tn⌋−⌈tn⌉+1)(⌊tn⌋−⌈t1⌉+1)
Then I found something magical .
⌊ n t ⌋ − ⌈ n t ⌉ + 1 = [ t ∣ n ] \left \lfloor \frac{n}{t}\right \rfloor-\left \lceil \frac{n}{t}\right \rceil+1=[t|n] ⌊tn⌋−⌈tn⌉+1=[t∣n],
⌈ 1 t ⌉ = 1 \left \lceil \frac{1}{t}\right \rceil=1 ⌈t1⌉=1,
So the original formula becomes φ ( n ) = ∑ t ∣ n μ ( t ) t \varphi(n)=\sum_{t|n}\mu(t)t φ(n)=∑t∣nμ(t)t, namely φ = μ ∗ i d \varphi=\mu*id φ=μ∗id.
There are many types , Do more questions .
Class is over , Sleep sleep
版权声明
本文为[Zimba_]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204230621425425.html
边栏推荐
- NLLLoss+log_ SoftMax=CE_ Loss
- SAP CR transmission request sequence and dependency check
- STM32 and FreeRTOS stack parsing
- SAP excel has completed file level validation and repair. Some parts of this workbook may have been repaired or discarded.
- Easy to understand subset DP
- SAP salv14 background output salv data can directly save files and send emails (with sorting, hyperlink and filtering format)
- Dropout技术之随机神经元与随机深度
- Random neurons and random depth of dropout Technology
- Simply understand = = and equals, why can string not use new
- Chapter VIII project stakeholder management of information system project manager summary
猜你喜欢
亚马逊云科技入门资源中心,从0到1轻松上云
Kettle实验 转换案例
How to obtain geographical location based on photos and how to prevent photos from leaking geographical location
PHP notes (I): development environment configuration
kernel-pwn学习(4)--Double Fetch&&0CTF2018-baby
LeetCode 1611. The minimum number of operations to make an integer 0
Leetcode题库78. 子集(递归 c实现)
JSON input of Chapter 14 of kettle paoding jieniu
[educational codeforces round 80] problem solving Report
Cloud identity is too loose, opening the door for attackers
随机推荐
ABAP implementation publishes restful services for external invocation example
Explanation of order and primitive root of number theory
Using sqlmap injection to obtain the account and password of the website administrator
Solving Lucas number and combination theorem
SAP pi / PO function operation status monitoring and inspection
KVM installation and deployment
php 二维数组指定元素相等后相加否则新增
Comparison of overloading, rewriting and hiding
ABAP CDs view with association example
亚马逊云科技入门资源中心,从0到1轻松上云
Applet error: should have URL attribute when using navigateto, redirectto or switchtab
1 + X cloud computing intermediate -- script construction, read-write separation
JS and how to judge custom attributes in H5
Kernel PWN learning (4) -- double fetch & 0ctf2018 baby
成功的DevOps Leader 应该清楚的3个挑战
SAP pi / PO soap2proxy consumption external WS example
Acquisition of DOM learning elements JS
JS DOM learn three ways to create elements
Chapter VIII project stakeholder management of information system project manager summary
Kettle实验 (三)