Mobius inversion

Preface ：

Just finished writing the product function , Two more today , More sleep .
 

Mobius function $\mu (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\ast 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$ Is a number theoretic function ,$f$ The value of the sum function of is $F(n)={\sum }_{d|n}f(d)$, Its value is determined by $f$ Decisive .
Now we're going to reverse this relationship , Let's get used to $F$ To solve $f$ The way to .
This is Mobius inversion .
We found that the original formula is actually $F=1\ast f$, Ride on both sides $\mu$, Got it. $f=\mu \ast 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)={\sum }_{d|n}f(d)$, Then there are $f(n)={\sum }_{d|n}\mu (d)F(n/d)$（ perhaps ${\sum }_{d|n}\mu (n/d)F(n)$）.

Then there is the second formula ,
It is known that $F(n)={\sum }_{n|d}f(d)$, Then there are $f(n)={\sum }_{n|d}\mu (d/n)F(d)$.（ This proof is slightly ）
 
in other words , When we ask for $f(n)$, however $f(n)$ It's not easy to ask , however $F(n)$ But unexpectedly good beg . that , After we learn Mobius inversion , You can go through this $F(n)$, To get $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]$ and $[c,d]$, How many reciprocal prime pairs of integers $x$ and $y$ Satisfy $a⩽x⩽b$ And $c⩽y⩽d$.$(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)$ Express satisfaction $t=gcd(x,y)$, And $a⩽x⩽b,c⩽y⩽d$ The logarithmic .
Then make $F(t)$ Express satisfaction $t|gcd(x,y)$, And $a⩽x⩽b,c⩽y⩽d$ The logarithmic .
Will find $F(t)$ You can ask directly ,$t|gcd(x,y)$ That is to say $t|x$ And $t|y$, That's how many $x$ By $d$ to be divisible by , How many $y$ By $d$ to be divisible by , Multiply it again . obtain $F(t)=(\lfloor \frac{b}{t}\rfloor -\lceil \frac{a}{t}\rceil +1)(\lfloor \frac{d}{t}\rfloor -\lceil \frac{c}{t}\rceil +1)$
And there are $F(n)={\sum }_{n|t}f(t)$,
After inversion, it becomes $f(n)={\sum }_{n|t}\mu (t/n)F(t)$.
So what we ask $f(1)={\sum }_{1|t}\mu (t)F(t).$
The next step is to enumerate $t$, The upper limit is $min(b,d)$.
 
Say another thing .
Look at the expression $[gcd(x,y)=1]$.
This reminds us of the unit function $e(n)=[n=1]$.
then $e=\mu \ast 1$, You can get an important expression ${\sum }_{d|n}\mu (d)=[n=1]$.
Then we start to push the formula ,
${\sum }_{x=a}^b{\sum }_{y=c}^d[gcd(x,y)=1]$
$={\sum }_{x=a}^b{\sum }_{y=c}^d{\sum }_{t|gcd(x,y)}\mu (t)$
$={\sum }_{x=a}^b{\sum }_{y=c}^d{\sum }_{t|x,t|y}\mu (t)$
$={\sum }_{t=1}^{min(b,d)}\mu (t){\sum }_{x=a}^b[t|x]{\sum }_{y=c}^d[t|y]$
$={\sum }_{t=1}^{min(b,d)}\mu (t)(\lfloor \frac{b}{t}\rfloor -\lceil \frac{a}{t}\rceil +1)(\lfloor \frac{d}{t}\rfloor -\lceil \frac{c}{t}\rceil +1)$
Then it's all right .
It's easy to get started , notice $[gcd(x,y)=1]$ Just put it in , And then put $gcd$ Mentioned earlier to enumerate , If it is $[gcd(x,y)=k]$, It turns into $1$ The situation of .
But it is necessary to study inversion carefully .
 
With integral division , It can also be optimized to $\sqrt{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 $\phi =\mu \ast 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]$ and $[n,n]$ Logarithm of Coprime in two intervals .
So we'll follow the derivation of the previous question , We get the formula ,
$\phi (n)={\sum }_{t=1}^n\mu (t)(\lfloor \frac{n}{t}\rfloor -\lceil \frac{n}{t}\rceil +1)(\lfloor \frac{n}{t}\rfloor -\lceil \frac{1}{t}\rceil +1)$
Then I found something magical .
$\lfloor \frac{n}{t}\rfloor -\lceil \frac{n}{t}\rceil +1=[t|n]$,
$\lceil \frac{1}{t}\rceil =1$,
So the original formula becomes $\phi (n)={\sum }_{t|n}\mu (t)t$, namely $\phi =\mu \ast id$.
 
 
 
 
 
There are many types , Do more questions .
Class is over , Sleep sleep