首页 > 其他分享 >欧拉函数与积性函数

欧拉函数与积性函数

时间：2023-08-06 22:12:04浏览次数：39  
标签：prime 函数 limits 积性 sum int ans 欧拉 gcd

\(Update\:\:on\:\:2023.8.3\)：增加了积性函数的内容，修改了内容排版

Part 1：欧拉函数及其性质

  • 定义：欧拉函数 \(φ(n)\) 表示小于等于 \(n\)，且与 \(n\) 互质的正整数的个数。

  • 公式：
    若在算数基本定理中，\(n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}\)（\(p\) 为质数），则由容斥原理：

    \[φ(n)=n*\dfrac{p_1-1}{p_1}*\dfrac{p_2-2}{p_2}*...*\dfrac{p_m-m}{p_m}=n*\prod\limits_{p\mid{n}}{(1-\dfrac{1}{p})}\qquad(p \in primes) \]

    关于此公式的证明，读者可自行推导

一些性质

  1. 若 \(n\) 是质数，则 \(φ(n)=n-1\)

  2. 若 \(n=p^k\)，且 \(p\) 为质数，则 \(φ(n)=(p-1)*p^{k-1}\)

  3. 若 \(p\) 是质数，且 \(\begin{cases}p\mid{n}&\Rightarrowφ(nq)=φ(n)*q\\p\nmid{n}&\Rightarrowφ(nq)=φ(n)*(q-1)\end{cases}\)

  4. \(n=\sum\limits_{d\mid{n}}{φ(d)}\)

  5. \(φ(ab)=φ(a)*φ(b)*\frac{d}{φ(d)}\)，其中 \(d=\gcd(a,b)\)

Part 2：积性函数

定义

若一个定义在正整数域上的函数 \(f\)，当 \(x,y\) 互质时，有 \(f(xy)=f(x)*f(y)\)，则称函数 \(f\) 是积性函数

特别地，当 \(x,y\) 不互质时仍有 \(f(xy)=f(x)*f(y)\) 的函数称为完全积性函数

常见完全积性函数：

  • \(ϵ(n)=[n=1]\)
  • \(I(n)=1\)
  • \(id_k(n)=n^k\)

常见积性函数

  • 欧拉函数 \(\varphi(n)\)
  • 莫比乌斯函数 \(\mu=I^{-1}\)
  • 除数函数 \(\sigma_k(n)=\sum\limits_{d\mid n}d^k\)
  • 除数函数 \(d(n)=\) \(n\) 的约数个数
  • \(s(n)=n\) 所有约数的和

一些乘积结论

  • \(\mu(ij)=[i\perp j]\mu(i)\mu(j)\)

  • \(φ(ab)=φ(a)*φ(b)*\frac{d}{φ(\gcd(a,b))}\)

  • \(d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[x\perp y]\)

  • \(\sigma_k(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[x\perp y](\frac{xj}{y})^k\)

除数函数的计算

对于 \(n=p_1^{c_1}p_2^{c_2}\dots p_m^{c_m}\)，有：

  • \(d(n)=(c_1+1)(c_2+1)\dots(c_m+1)\)

    记 \(p\) 为 \(n\) 的最小质因子，有：

    \[d(n)=\begin{cases}2d(n/p)-d(n/p^2)&p^2\mid n\\2d(n/p)&\rm otherwise\end{cases} \]

  • \(\sigma_k(n)=\prod\limits_{i=1}^m(1+p_i+p_i^2+\dots+p_i^{c_i})\)

Part 3：欧拉函数例题

【模板题】求 φ(n)

解题思路

  • 我们已知 \(φ(n)\) 的计算公式，所以只需对 \(n\) 进行质因数分解即可

代码

#include<bits/stdc++.h>
using namespace std;

const int N=100001;

int n;

int GetPhi(int n)
{
	int ans=n;
	for(int i=2; i*i<=n; i++) //分解质因数
	{
		if(n%i==0)
		{
			ans=ans*(i-1)/i; //计算公式
			while(n%i==0)
				n/=i;
		}
	} 
	
	if(n>1) //还剩下一个较大的质数
		ans=ans*(n-1)/n;
	
	return ans;	
}

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

【模板题】求 φ(1) ~ φ(n)

解题思路

  • 由于欧拉函数是积性函数，所以我们考虑用线性筛求解

  • 从欧拉函数性质 \(3\) 出发，在线性筛中，每个合数 \(x\) 都会被它最小的质因子 \(p\) 筛去，此时我们就可以用 \(p\) \((\)或 \(p-1)\) 和 \(φ(x/p)\) 来推出 \(φ(x)\) ，具体是 \(p\) 还是 \(p-1\)，要看 \(x/p\)，即我们外层循环的 \(i\) 是否是 \(q\) 的倍数；而对于每个质数 \(y\)，由性质 \(1\) 可得：\(φ(y)=y-1\)

代码

#include<bits/stdc++.h>
using namespace std;

const int N=100001;

int n,phi[N],v[N],prime[N],tot;

void GetPhi(int n)
{
	phi[1]=1;
	for(int i=2; i<=n; i++)
	{
		if(!v[i])
		{
			v[i]=i;
			prime[++tot]=i;
			phi[i]=i-1;
		}
		
		for(int j=1; j<=tot; j++)
		{
			if(prime[j]>v[i] || prime[j]>n/i)
				break;
			v[i*prime[j]]=prime[j];
			if(i%prime[j]==0)
				phi[i*prime[j]]=prime[j]*phi[i];
			else
				phi[i*prime[j]]=(prime[j]-1)*phi[i];
		} 
	}
}

int main()
{
	cin>>n;
	
	GetPhi(n);
	
	for(int i=1; i<=n; i++)
		cout<<phi[i]<<" ";
		
	return 0;
}

【练习题】公约数的和

（题目传送门）

题目大意

给定 \(n\)，求

\[\sum\limits_{i = 1}^n \sum\limits_{j = i + 1}^n \gcd(i, j) \]

其中 \(\gcd(i, j)\) 表示 \(i\) 和 \(j\) 的最大公约数。

解题思路

  • 我们记 \(ans=\sum\limits_{i = 1}^n \sum\limits_{j = i + 1}^n \gcd(i, j)\)

  • 改写一下可得：

    \[ans=\dfrac{\sum\limits_{i = 1}^n \sum\limits_{j =1}^n \gcd(i, j)-\sum\limits_{i=1}^n\gcd(i,i)}{2} \]

    \[=\dfrac{\sum\limits_{i = 1}^n \sum\limits_{j =1}^n \gcd(i, j)-\sum\limits_{i=1}^ni}{2} \]

  • 那么我们枚举最大公约数 \(d\)，设 \(f(d)\) 表示有多少对 \((i,j)\) 使得 \(\gcd(i,j)=d\)，那么就有

    \[ans=\dfrac{\sum\limits_{d=1}^n{d*f(d)} -\sum\limits_{i=1}^ni}{2} \]

  • 进一步思考，若整数对 \((i,j)\) 满足 \(\gcd(i,j)=d\)，则有：\(i\mid d,\: j\mid d,\:\gcd(i/d,j/d)=1\)。

  • 设 \(x=i/d,\:y=j/d\)，下面分 \(3\) 种情况讨论对于每一个 \(x\)，有多少个 \(y\) 满足 \(\gcd(x,y)=1\)：

    1、若 \(i>j\)，则 \(x>y\)。又因为 \(j<i \leqslant n\)，所以 \(y<x \leqslant n/d\)。那么满足 \(\gcd(x,y)=1\) 的 \(y\) 的数量就为 \(1\) ~ \(x\) 里与 \(x\) 互质的数的个数，即 \(φ(x)\)。

    2、若 \(i<j\)，则 \(x<y\)，那么令 \(x'=y,\:y'=x\)，那么此时的答案即为第 1 种情况中已求出的满足 \(\gcd(x',y')=1\) 的 \(y\) 的数量。所以答案为 \(φ(x')\)。因此，每一个 \(φ(x)\) 都会被算 \(2\) 遍

    3、若 \(i=j\)，则 \(x=y\)，此时 \(y\) 的取值很明显只有 \(1\) 种

  • 综上，

    \[f(d)=(\sum\limits_x^{n/d}{φ(x)})*2+1 \]

  • 在求 \(f(d)\) 前，可对 \(φ()\) 进行前缀和的预处理，节省时间

代码

#include<bits/stdc++.h>
using namespace std;

const int N=2000010;

int n,phi[N],v[N],prime[N],tot;
long long ans,sum[N],f[N];

void GetPhi(int n) //求phi[1~n]
{
	phi[1]=1;
	for(int i=2; i<=n; i++)
	{
		if(!v[i])
		{
			v[i]=i;
			prime[++tot]=i;
			phi[i]=i-1;
		}
		
		for(int j=1; j<=tot; j++)
		{
			if(prime[j]>v[i] || prime[j]>n/i)
				break;
			v[i*prime[j]]=prime[j];
			if(i%prime[j]==0)
				phi[i*prime[j]]=prime[j]*phi[i];
			else
				phi[i*prime[j]]=(prime[j]-1)*phi[i]; 
		} 
	}
	
	for(int i=1; i<=n; i++) //前缀和预处理
		sum[i]=sum[i-1]+(long long)phi[i]; 
}

int main()
{	
	cin>>n;
	
	GetPhi(n);
	 	 
	for(int i=1; i<=n; i++)
		f[i]=sum[n/i]*2-1,ans+=f[i]*(long long)i; //求f和ans
	
	ans=(ans-(long long)(1+n)*n/2)/2; //最后一步
	
	cout<<ans;
	
	return 0;
}

【练习题】GCD(x,n)>=m

题目大意

给定整数 \(n\) 和 \(m\)，问题是求有多少个整数 \(x\)，满足 \(1 \leqslant x \leqslant n\) 且 \(\gcd(x,n) \geqslant m\)。

解题思路

  • 记 \(\gcd(x,n)=d\)，那么由定义得：\(d \mid n\) 。因此我们考虑去枚举 \(n\) 的约数，并舍去其中小于 \(m\) 的约数，那么剩下的数便可以作为 \(d\) 的取值。

  • 对于大于等于 \(m\) 的约数 \(i\)，由上一题的解题思路可知：\(x\mid i\) 且 \(\gcd(x/i,n/i)=1\)，所以答案便为 \(φ(n/i)\)

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int T,n,m;
LL ans;

LL GetPhi(int n) //求phi[n]
{
	LL ans=(LL)n;
	for(int i=2; i*i<=n; i++)
	{
		if(n%i==0)
		{
			ans=ans*(LL)(i-1)/i;
			while(n%i==0)
				n/=i;
		}
	} 
	
	if(n>1)
		ans=ans*(LL)(n-1)/n;
	
	return ans;	
}


int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		ans=0;
		
		for(int i=1; i*i<=n; i++) //枚举约数
		{
			if(n%i==0)
			{
				if(i>=m) //约数i
					ans=ans+(LL)GetPhi(n/i);
				if(i!=n/i && n/i>=m) //由于约数成对出现,所以n/i也是n的约数,注意要避免完全平方数的情况
					ans=ans+(LL)GetPhi(i);
			}
		}
		
		printf("%lld\n",ans);
	}
	
	return 0;
}

【练习题】非互质数求和

题目大意

如果一个正整数 \(x\) 小于 \(n\)，而且 \(x\) 与 \(n\) 不互质，那么整数 \(x\) 称为“好数”。

给定一个正整数 \(n\)，求所有的“好数”的和。

这里互质的定义：如果 \(A,B\) 除 \(1\) 外没有其他的公因数，则称 \(A\) 与 \(B\) 互质。

答案模 \(1000000007\)。

解题思路

  • 考虑到正面求解较难，我们可以考虑求答案的补集，即求所有与 \(n\) 互质的数的和

  • 在这我们先引入一个结论：

    \[\gcd(n,x)=\gcd(n,n-x) \]

    这个结论我们最后会来证明。

    那么如果 \(x\) 与 \(n\) 互质，由结论就可知 \(n-x\) 也与 \(n\) 互质

  • 设集合 \(X\) 为与 \(n\) 互质的数的集合。则集合元素个数为 \(φ(n)\)，集合元素分别为 \(x_1,x_2\:......\:x_{φ(n)}\)。由刚刚的结论可知 \(x_i+x_{φ(n)-i+1}=n\)，这样的数对共有 \(φ(n)/2\) 个，所以 \(\sum\limits_{i=1}^{φ(n)}{x_i}=\dfrac{n*φ(n)}{2}\)

  • 最后答案即为 \(\sum\limits_{i=1}^{n-1}{i}-\dfrac{n*φ(n)}{2}\)

关于引入结论的证明

  • 设 \(d=\gcd(n,x)\)，则有 \(n=k_1d,\:x=k_2d\) 且 \(\gcd(k_1,k_2)=1 \quad (k_1,k_2 \in \mathbb{N^*})\)，那么 \(n-x=(k_1-k_2)d\)

  • 假设 \(\gcd(n,n-x) \ne d\)，则 \(\gcd(k_1,k_1-k_2) \ne 1\)。所以可设 \(k_1=ab,k_1-k_2=ac\ (a\ne 1,\quad a,b,c \in \mathbb{N^*})\)，那么可推出 \(k_2=a(b-c)\)，易知 \(b-c \ne 0\)，所以 \(\gcd(k_1,k_2) \ne 1\)，因此假设矛盾

  • 综上，\(\gcd(n,x)=\gcd(n,n-x)\)

代码

#include<bits/stdc++.h>
using namespace std;

const long long MOD=1000000007;

long long n; 

long long GetPhi(long long m)  //求phi[n]
{
	long long ans=m;
	for(int i=2; i*i<=m; i++)
	{
		if(m%i==0)
		{
			ans=ans*(i-1)/i;
			while(m%i==0)
				m/=i;
		}
	}
	
	if(m>1)
		ans=ans*(m-1)/m; 
	
	return ans;
}

int main()
{
	while(scanf("%lld",&n))
	{
		if(n==0)
			break;
		
		printf("%lld\n",(n*(n-1)/2-n*GetPhi(n)/2)%MOD);
	}
	
	return 0;
}

【练习题】USB的数学题

题目大意

求 \(F(n)=\sum\limits_{i=1}^n{\dfrac{n}{\gcd(i,n)}}\) 的值

\(T\) 组测试数据（\(T,n \leqslant 10^7\)）

解题思路

  • 设 \(d=\gcd(i,n)\)，则满足 \(\gcd(i,n)=d\) 的 \(i\) 的个数就为 \(φ(n/d)\)。所以 \(F(n)\) 可写成

    \[F(n)=\sum\limits_{d\mid n}^{}{φ(d)*d} \]

  • 再看一眼数据范围，显然对于每组测试数据的每个 \(n\)，都进行根号级别的枚举是无法拿到满分的，所以我们要思考 \(F(n)\) 所具有的其它性质——没错，积性函数！

  • \(F\) 是积性函数是很好证明的。设 \(x,y\) 为互质的两个正整数。则 \(F(x)=\sum\limits_{a\mid x}^{}{(φ(a)*a)},\:F(y)=\sum\limits_{b\mid y}^{}{(φ(b)*b)}\)。那么 \(F(x)*F(y)=\sum\limits_{a\mid x}^{}{(φ(a)*a)}*\sum\limits_{b\mid y}^{}{(φ(b)*b)}\:\)。由于 \(x\) 与 \(y\) 互质，所以 \(a\) 与 \(b\) 也是互质的，再加上 \(φ\) 是积性函数，所以

    \[F(x)*F(y)=\sum\limits_{ab\mid xy}^{}{φ(ab)*ab}=F(xy) \]

    因此，\(F\) 是积性函数

  • 一开始我们已经说过，所有的积性函数都可以用线性筛求解。本题我们分 \(3\) 种情况对 \(F\) 的递推进行讨论：

    1、当 \(n=10\) 时，\(10\) 的最小质因子为 \(2\)，\(2\) 与 \(10/2=5\) 互质，所以 \(F(10)\) 可以由 \(F(2)*F(5)\) 得到。这是最简单的一种情况。

    2、当 \(n=12\) 时，\(12\) 的最小质因子为 \(2\)，但 \(2\) 与 \(12/2=6\) 不互质，所以此时无法直接递推。因为 \(12=2^2*3\)，所以我们需要令 \(a=2^2,\:b=3\)，这样 \(a\) 与 \(b\) 一定是互质的，再通过 \(F(a)*F(b)\) 得到 \(F(12)\)。因此，我们需要记录每一个数的最小质因子的最高次幂的值，记为 \(highPow[n]\)。对于这种情况，我们就可以令 \(a=highPow[n],b=n/a\)，再通过 \(F(a)*F(b)\) 得到 \(F(n)\)

    3、当 \(n=8\) 时，\(a=highPow[8]=8,\:b=8/a=1\)，就会产生 \(F(8)=F(8)*F(1)\) 这样的情况，所以我们还需要记录 \(n\) 的最小质因子的指数，记为 \(mi[n]\)。那么当 \(n=x^{mi[n]}\) 时，我们可以暴力求解 \(F(n)=\sum\limits_{d\mid n}^{}{φ(d)*d}\:\)。显然我们有 \(F(n)=\sum\limits_{i=1}^{mi[n]}{x^i*φ(x^i)}+1\:\) (\(+1\)是当 \(d=1\) 的情况)。由 \(φ\) 的计算公式，我们就可以得到：

    \[F(n)=\sum\limits_{i=1}^{mi[i]}{x^i*x^i*(1-\dfrac{1}{x})}+1 \]

    \[=\sum\limits_{i=1}^{mi[i]}{x^i*x^i*(\dfrac{x-1}{x})}+1 \]

    \[=\sum\limits_{i=1}^{mi[i]}{x^i*x^{i-1}*(x-1)}+1 \]

    我们再通过一个简单的前缀积处理，就可以暴力的求解这种情况的 \(F(n)\)

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=10000010;

int T,n;
int v[N],prime[N],tot;
LL f[N],highPow[N],mi[N],tmp[N];

void prework(int n)
{
	f[1]=1;
	for(int i=2; i<=n; i++)
	{
		if(!v[i])
		{
			v[i]=i;
			prime[++tot]=i;
			f[i]=(LL)(i-1)*i+1;
			highPow[i]=i;
			mi[i]=1;
		}
		
		for(int j=1; j<=tot; j++)
		{
			if(prime[j]>v[i] || prime[j]>n/i)
				break;
				
			int x=i*prime[j];
			v[x]=prime[j];
			
			if(i%prime[j]!=0) //第1种情况(由于prime[j]是质数,所以i与prime[j]互质当且仅当i不是prime[j]的倍数或约数)
			{
				highPow[x]=prime[j];
				mi[x]=1;
				f[x]=f[i]*f[prime[j]];
			}
			else
			{
				highPow[x]=highPow[i]*prime[j];
				mi[x]=mi[i]+1;
				
				int a=highPow[x],b=x/a;
				if(b==1) //第3种情况
				{
					tmp[0]=1;
					for(int i=1; i<=mi[x]; i++)
						tmp[i]=tmp[i-1]*(LL)prime[j]; //前缀积处理prime[j]的幂
					for(int i=1; i<=mi[x]; i++)
						f[x]+=tmp[i]*tmp[i-1]*(LL)(prime[j]-1); //暴力求解
					f[x]++; //加上d=1的情况
				}
				else //第2种情况
					f[x]=f[a]*f[b];
			}
		} 
	}
}

int main()
{
	prework(N-10);
	
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		printf("%lld\n",f[n]);
	}
	
	return 0;
}

标签：prime,函数,limits,积性,sum,int,ans,欧拉,gcd
From： https://www.cnblogs.com/xishanmeigao/p/17610169.html

相关文章

  • C与C++之间的相互调用及函数区别
    最近项目需要使用googletest（以下简称为gtest）作为单元测试框架，但是项目本身过于庞大，main函数无从找起，需要将gtest框架编译成静态库使用。因为项目本身是通过纯c语言编写，而gtest则是一个c++编写的测试框架，其中必然涉及c与c++之间的相互调用。注意，本文的前提是，c代码采用gcc等c语言编......
  • 【JavaScript17】eval函数
    eval本身在js里面正常情况下使用的并不多.但是很多网站会利用eval的特性来完成反爬操作.我们来看看eval是个什么鬼?从功能上讲,eval非常简单.它和python里面的eval是一样的.它可以动态的把字符串当成js代码进行运行.vars="1+2+3+4+5+6+7+8";varc=eval(s);//帮你......
  • 【JavaScript14】函数基础
    函数定义函数定义的方法有多种，主要分为函数声明和函数表达式//函数声明functionfunc(arg1,arg2){console.log("arg1=",arg1);console.log("arg2=",arg2);return"返回一些东西"}varret=func("苹果","鸭梨");console.log(......
  • 使用print()函数控制小数位
     方法一：round(x,N)这种方法不是严格有效的，当数字总的小数位小于控制输出的小数位时没有效果。num=3.1round(3.1,2)3.1round(3.141,2)3.14round(3,2)3  方法二：print("%.nf"%x)'%.2f'%3.1'3.10''%.2f'%3.1415'3.14' 方法三：print(form......
  • 无涯教程-Perl - dbmopen函数
    描述此函数将EXPR指定的数据库文件绑定到哈希HASH。如果数据库不存在,则使用MODE指定的模式创建数据库。文件EXPR的扩展名应不含.dir和.pag。现在不赞成使用领带,而是使用领带DBM哈希模块之一,例如SDBM_File。语法以下是此函数的简单语法-dbmopenHASH,EXPR,MOD......
  • 无涯教程-Perl - continue函数
    描述此函数是流控制语句,而不是函数。如果在块上附加了一个连续块(通常在while或foreach中),则它总是在条件将要再次求值之前执行,就像C中for循环的第三部分一样。因此,即使通过next语句继续执行循环,也可以使用它来增加循环变量。最后,下一个或重做可能会出现在继续块中。......
  • 数组,条件,循环,重要函数,超级全局变量,魔术方法
    目录数组,条件,循环,实战重要函数超级全局变量魔术方法数组,条件,循环,实战数组在PHP中，array()函数用于创建数组：$cars=array("Volvo","BMW","Toyota");在PHP中，有三种类型的数组：数值数组-带有数字ID键的数组关联数组-带有指定的键的数组，每个键关联一个值......
  • 无涯教程-Perl - closedir函数
    描述此功能关闭目录句柄DIRHANDLE。语法以下是此函数的简单语法-closedirDIRHANDLE返回值如果失败,此函数返回0,如果成功,则返回1。例以下是显示其基本用法的示例代码-#!/usr/bin/perl-w$dirname="/tmp";opendir(DIR,$dirname)||die"Errorinopeningd......
  • 无涯教程-Perl - chroot函数
    描述此函数的工作方式类似于具有相同名称的系统调用:它使命名目录成为您的进程及其所有子级以/开头的所有其他路径名的新根目录。出于安全原因,该功能与系统chroot()功能相同,仅限于超级用户且无法撤消。如果省略了FILENAME,则对$_执行chroot语法以下是此函数的简单语法-ch......
  • 无涯教程-Perl - chown函数
    描述此功能更改文件列表的所有者(和组)。列表的前两个元素必须是按顺序排列的数字uid和gid。此功能调用的工作方式与unix命令chown相似。因此,您应该具有足够的特权来更改文件的权限。语法以下是此函数的简单语法-chownUSERID,GROUPID,LIST返回值此函数返回成功更改的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99