欧拉函数和莫比乌斯反演（Mobius）

时间：2023-01-08 22:31:25

这几天研究了之前一直困扰自己很久的莫比乌斯反演，虽然自己现在学的还不是很好，就简简单单的写一下总结吧，咦，都没学会掌握我就写总结好像很欠揍，欧拉函数现在也系统的整理一下好了

一、欧拉函数

1.定义：在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。此函数以其首名研究者欧拉命名(Euler’so totient function)，它又称为Euler’s totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。
设n为正整数，以 φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值
φ：N→N，n→φ(n)称为欧拉函数。
2.函数内容：
通式： 欧拉函数和莫比乌斯反演（Mobius）
其中p1, p2……pn为x的所有质因数，x是不为0的整数。

至于欧拉函数的一些性质可以见以下博客：
求逆元的博客

3.之后给出几种求欧拉函数的代码：（建议看这一篇博客）
（1）筛法求欧拉函数的代码：

//筛法欧拉函数

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=3e6+10;

int euler[N];


void getEuler()
{
memset(euler,0,sizeof(euler));
    euler[1]=1;
for(int i=2; i<N; i++)
    {
if(euler[i]==0)
        {
for(int j=i; j<N; j++)
            {
if(euler[j]==0)
                    euler[j] = j;
                euler[j] = euler[j]/i*(i-1);
            }
        }
    }
}

int main()
{
    getEuler();
int n;
cin>>n;
cout<<euler[n]<<endl;
return 0;
}

（2）求单个数的欧拉函数：

//求单个数的欧拉函数 也就是所谓的直接求

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define ll long long
const int N=3e6+10;

ll eular(ll n)
{
    ll ans = n;
for (int i = 2; i*i <=n; i++)
    {
if(n%i==0)
        {
            ans-=ans/i;
while( n % i == 0)
                n /= i;
        }
    }
if(n>1)
        ans -= ans/n;
return ans;
}

int main()
{
int n;
cin>>n;
cout<<eular(n)<<endl;
return 0;
}

（3）线性筛求欧拉函数（同时得到欧拉函数和素数表）：

//线性筛的时间复杂度为O(n)
//
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define ll long long
const int N=3e6+10;
bool check[N];
int phi[N];//
int prime[N];//素数
int tot;

void phi_and_prime_table(int x)
{
memset(check,false,sizeof(check));
    phi[1]=1;
    tot = 0;
for(int i = 2; i <= x; i++)
    {
if( !check[i])//i是素数
        {
            prime[tot++] = i;
            phi[i] =i-1;
        }
for(int j=0; j < tot; j++)
        {
if(i* prime[j]>x)
break;
            check[i*prime[j]]=true;
if( i % prime[j] == 0)
            {
                phi[i*prime[j]]=phi[i] * prime[j];
break;
            }
else
            {
                phi[i *prime[j]]=phi[i] * (prime[j]-1);
            }

        }
    }
}

int main()
{
int n;

cin>>n;
    phi_and_prime_table(n);
cout<<phi[n]<<endl;
return 0;
}

（4）分解质因数求欧拉函数：在这里不给出详细代码了

以上即欧拉函数的知识点及代码模板，接下来开始介绍莫比乌斯反演

二、莫比乌斯反演

1.定理：F(n)和f(n)是定义在非负整数集合上的两个函数，并且满足条件欧拉函数和莫比乌斯反演（Mobius）
则我们得到结论欧拉函数和莫比乌斯反演（Mobius）

其中u(d)为莫比乌斯函数，定义如下：
（1）若 d=1，那么 u（d）=1
（2）若d=p1*p2*p3····*pk，pi均为互异素数，则u（d）=（-1）^k
（3）其它情况下 u(d)=0

对于u（d）函数有以下常见的性质：
（1）对任意正整数n 有 欧拉函数和莫比乌斯反演（Mobius）
（2）对任意正整数n有欧拉函数和莫比乌斯反演（Mobius）

2.证明：
欧拉函数和莫比乌斯反演（Mobius）

3.线性筛选求莫比乌斯函数：

​​//线性筛求莫比乌斯反演
//
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define ll long long
const int N=3e6+10;
ll mob[N];
ll vis[N];
ll prime[N];//素数
ll cnt;

void Mobius()
{
memset(prime,0,sizeof(prime));
memset(mob,0,sizeof(mob));
memset(vis,0,sizeof(vis));
    mob[1] = 1;
    cnt = 0;
for(ll i = 2; i <N; i++)
    {
if( !vis[i])
        {
            prime[cnt++] = i;
            mob[i]=-1;
        }
for(ll j=0; j < cnt&&i*prime[j]<N; j++)
        {
            vis[i*prime[j]]=1;
if(i%prime[j])
                mob[i*prime[j]]=-mob[i];
else{
            mob[i*prime[j]]=0;break;}
        }
    }
}

int main()
{
int n;
    Mobius();
cin>>n;
cout<<mob[n]<<endl;
return 0;
}

嗯 先写到这，等这几天自己理解更深刻的时候就回来补充

标签：

相关文章