首页 > 其他分享 >欧拉函数

欧拉函数

时间:2023-04-07 20:55:23浏览次数:47  
标签:lfloor right 函数 cdot dfrac rfloor 欧拉 left

欧拉函数 \(\phi\)

定义

\(\phi(n)\) 表示 \(1 \sim n\) 中与 \(n\) 互质的数的个数。

公式

先将 \(n\) 分解质因数,即:

\(n = p_1^{\alpha_1} \cdot p_2^{\alpha_2}\ \dots p_k^{\alpha_k}\)

则 \(\phi(n) = n \cdot \prod_{i=1}^k (1-\dfrac{1}{p_i})\)。

即 \(\phi(n) = n \cdot \left(1-\dfrac{1}{p_1}\right)\cdot \left(1-\dfrac{1}{p_2}\right)\dots\left(1-\dfrac{1}{p_k}\right)\)

也可以写成 \(\phi(n) = n \cdot \dfrac{p_1-1}{p_1}\cdot \dfrac{p_2-1}{p_2}\dots\dfrac{p_k-1}{p_k}\)

例如:

\(n = 6 = 2^1 \cdot 3^1\)

\(\phi(6) = 6 \cdot \left(1-\dfrac12 \right) \cdot \left(1-\dfrac13 \right) = 2\)

\(\phi(6) = 6 \cdot \dfrac{2-1}2 \cdot \dfrac{3-1}3 = 2\)

依据

容斥原理

推导

  1. 从 \(1 \sim n\) 中去掉 \(p_1,p_2,\dots,p_k\) 的所有倍数,即 \(n \gets n-\left \lfloor \dfrac{n}{p_1} \right \rfloor - \left \lfloor \dfrac{n}{p_2} \right \rfloor - \dots - \left \lfloor \dfrac{n}{p_k} \right \rfloor\)。
  2. 加上所有 \(p_i \cdot p_j\) 的倍数,即 \(n \gets n+\left \lfloor \dfrac{n}{p_1 \cdot p_2} \right \rfloor + \left \lfloor \dfrac{n}{p_1 \cdot p_3} \right \rfloor + \dots + \left \lfloor \dfrac{n}{p_{k-1} \cdot p_k} \right \rfloor\)。
  3. 减去所有 \(p_i \cdot p_j \cdot p_k\) 的倍数,即 \(n \gets n-\left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3} \right \rfloor - \left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_4} \right \rfloor - \dots - \left \lfloor \dfrac{n}{p_{k-2} \cdot p_{k-1} \cdot p_k} \right \rfloor\)。
  4. 加上所有 \(p_i \cdot p_j \cdot p_k \cdot p_l\) 的倍数,即 \(p_i \cdot p_j \cdot p_k\) 的倍数,即 \(n \gets n+\left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3 \cdot p_4} \right \rfloor + \left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3 \cdot p_5} \right \rfloor + \dots +- \left \lfloor \dfrac{n}{p_{k-3} \cdot p_{k-2} \cdot p_{k-1} \cdot p_k} \right \rfloor\)。

\[\Large \vdots \]

因此,

$\phi(n) = $

\(n-\left \lfloor \dfrac{n}{p_1} \right \rfloor - \left \lfloor \dfrac{n}{p_2} \right \rfloor - \dots - \left \lfloor \dfrac{n}{p_k} \right \rfloor\)

\(+\left \lfloor \dfrac{n}{p_1 \cdot p_2} \right \rfloor + \left \lfloor \dfrac{n}{p_1 \cdot p_3} \right \rfloor + \dots + \left \lfloor \dfrac{n}{p_{k-1} \cdot p_k} \right \rfloor\)

\(-\left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3} \right \rfloor - \left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_4} \right \rfloor - \dots - \left \lfloor \dfrac{n}{p_{k-2} \cdot p_{k-1} \cdot p_k} \right \rfloor\)

\(+\left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3 \cdot p_4} \right \rfloor + \left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3 \cdot p_5} \right \rfloor + \dots +- \left \lfloor \dfrac{n}{p_{k-3} \cdot p_{k-2} \cdot p_{k-1} \cdot p_k} \right \rfloor\)

\(- \dots\)

也就是 \(n\) 减去奇数个质因子的倍数,加上偶数个质因子的倍数,循环往复。

将上式等价变形,得到刚才提到的公式。

代码

cin >> n;
res = n;	// 初始值为 n 

for(int i=2; i<=n/i; i++){
	// 如果 i 是 n 的质因子 
    if(n%i == 0){
        res = res / i * (i - 1);
    	// 或 res * (1 - 1 / i);
    	// 或 res * ((i - 1) / i);
    	// 但如果使用后面 2 种,则需要考虑实数问题 
        while(n%i == 0){
            n /= i;
        }
    }
}

// 如果还剩下大于根号 n 的质因子,再次统计到答案种 
if(n > 1){
    res = res / n * (n - 1);
}

cout << res;

求多个数欧拉函数之和

求 \(1\) 个数的欧拉函数时间复杂度是 \(\Theta(\sqrt{n})\),求 \(n\) 个数的时间复杂度即 \(\Theta(n \cdot \sqrt{n})\),那如何进行优化,使其变成 \(\Theta(n)\) 呢?

可以先线性地筛出 \(n\) 以内的所有质数,在进行求解。

线性筛指数的代码如下:

for(int i=2; i<=n; i++){
    if(!st[i]){
        p[cnt++] = i;
    }
    for(int j=0; p[j] <= n/i; j++){
        st[p[j] * i] = 1;
        if(i%p[j] == 0){
            break;
        }
    }
}

如何对其进行修改呢?

边界条件

从定义出发设置边界条件,即 \(\phi(1) = 1\)。

如果 \(i\) 是质数

如果 \(i\) 是质数,那么在 \(1 \sim n\) 当中 \(1 \sim n-1\) 都是与其互质的数,即 \(\phi(i) = i-1\)。

内层循环

如果 \(p_j\) 是 \(i\) 的最小质因子

因为一个数分解质因数后的指数与欧拉函数结果无关,因此 \(p_j \cdot i\) 和 \(i\) 的质因子是相同的,因为将 \(p_j \cdot i\) 和 \(i\) 分解质因数后,\(p_j \cdot i\) 只会比 \(i\) 的指数多1。

我们假设 \(i\) 的质因子是 \(q_1,q_2,\dots,q_k\),那么 \(\phi(i) = i \cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right)\)。

由于 \(p_j\) 是 \(i\) 的质因子,又因为 \(p_j \cdot i\) 的质因子与 \(i\) 相同,那么,

\(\phi(p_j\cdot i) = p_j \cdot i\cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right)\)。

其中的 \(i\cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right)\) 与 \(\phi(i)\) 相同,所以我们可以下结论:

\[\phi(p_j \cdot i) = p_j \cdot \phi(i) \]

如果 \(p_j\) 不是 \(i\) 的最小质因子

那么 \(p_j\) 就是 \(p_j \cdot i\) 的最小质因子,且 \(p_j\) 是不包含在 \(i\) 的质因子当中的。

因此,假设 \(i\) 的所有质因子是 \(q_1, q_2,\dots,q_k\),那么 \(\phi(i) = i \cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right)\)。

则 \(\phi(p_j \cdot i) = p_j \cdot i \cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right) \cdot \left(1-\dfrac{1}{p_j}\right)\)。

其中的 \(i\cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right)\) 与 \(\phi(i)\) 相同,所以我们可以下结论:

\[\phi(p_j \cdot i) = p_j \cdot \phi(i) \cdot \left( 1-\dfrac{1}{p_j}\right) = \phi(i) \cdot (p_j - 1) \]

代码

int get_phi(int n){
    phi[1] = 1;     // 特殊规定
    for(int i=2; i<=n; i++){
        if(!st[i]){
            p[cnt++] = i;
            phi[i] = i - 1;     // 如果 i 是质数,它的欧拉函数是 i-1
        }
        for(int j=0; p[j] <= n/i; j++){
            st[p[j]*i] = 1;     // p[j] * i 不是质数
            if(i % p[j] == 0){  // p[j] 是 i 的最小质因子
                phi[p[j] * i] = phi[i] * p[j];
                break;
            }
            else{   // p[j] 是 p[j] * i 的最小质因子
                phi[p[j] * i] = phi[i] * (p[j] - 1);
            }
        }
    }
    int res = 0;
    // 统计所有数的欧拉函数之和
    for(int i=1; i<=n; i++){
        res += phi[i];
    }
    // 返回
    return res;
}

欧拉定理

若 \(a\) 与 \(n\) 互质,则有 \(a^{\phi(n)} \equiv 1 (\bmod\ n)\)。

标签:lfloor,right,函数,cdot,dfrac,rfloor,欧拉,left
From: https://www.cnblogs.com/2huk/p/17297307.html

相关文章

  • cmake 函数编译第三方库
    function(find_external_project_add)set(optionsBUILD_SHARED_LIBRARY)set(oneValueArgsNAME)set(multiValueArgsDEPENDSEXPORT_LIBRARIESCONFIGURE_COMMANDSEXTRA_LINKS)cmake_parse_arguments(Argument"${options}""${oneValueArgs......
  • SQL Server STUFF() 函数详解
    STUFF():在SQLServer中,stuff()函数用于从源字符串中删除给定长度的字符序列,并从指定的起始索引插入给定的字符序列。用法:STUFF(source_string,start,length,change_string)source_string:字符数据start:指定删除和插入的开始位置length:指定要删除的字符数......
  • 箭头函数
    ?ES6+新特性,是函数的新写法useconstfn=(x,y)=>{returnx+y}console.log(fn(1,2));箭头函数的this指向箭头函数的this值会指向它上一级的作用域(函数),直接定义箭头函数,它的this就直接指向window了,注意在DOM事件的时候避免用箭头函数......
  • 什么是虚拟函数 —— C++ 开发人员应该如何充分利用它?
    什么是虚拟函数?虚拟函数是基类中声明的成员函数,且使用者期望在派生类中将其重新定义。那么,在C++中,什么是虚拟函数呢?在C++中,通常将虚拟函数用于实现运行时多态,该特性由C++提供,适用于面向对象编程。我们将在下文更为详细地讨论运行时多态。不论函数调用所使用的指针或引用类型......
  • Shell函数
    定义[function]funName(){ action; [returnint;]}可以带functionfun()定义,也可以直接fun()定义,不加任何参数。参数返回,可以显示加return返回,如果不加,将以最后一条命令运行结果,作为返回值。return后跟的值(0-255)-----------demoFun(){echo"这是我的第一个shell函数!"}ech......
  • Oracle中的单行函数
    一.定义单行函数为查询的表或视图的每一行返回一个结果行。这些函数可以出现在可以出现在SELECT列中,WHERE子句,STARTWITH和CONNECTBY子句以及HAVING子句中。单行函数大致分为:数值函数,字符函数,日期时间函数,转换函数,和通用函数。二.数值函数数值函数接受数值输......
  • 获取Python函数信息的方法
    Python的反射机制可以动态获取对象信息以及动态调用对象,本文介绍如何获取对象中的函数注释信息以及参数信息。定义一个Person类:classPerson():deftalk(self,name,age,height=None):"""talkfunction:return:"""print(f"Mynamei......
  • C++虚函数
    形式:virtual函数类型函数名()(在派生类和基类里都要写)静态成员函数不能是虚函数1.通过指针实现多态对于基类的对象:调用基类的虚函数对于派生类的对象:调用派生类的虚函数#include<iostream>usingnamespacestd;classA{ public: virtualvoidPrint() { cout<<"printA"......
  • C++知晓某个key值,调用相应的类函数
    1、类函数中定义一个map表typedefint(CClassTest::*pfnMethodExe)(std::stringstrInput,intnInputNum); std::map<std::string,pfnMethodExe>m_fnMethodExecute;CClassTest为类名,typedefint中的int为函数返回值,可以为其他值2、key值和函数对应关系放入map表中m_fnMeth......
  • Python中的时间函数strftime与strptime对比
    一、striftime将给定格式的日期时间对象转换为字符串。日期时间对象=>字符串,控制输出格式.date、datetime、time对象都支持strftime(format) 方法,可用来创建由一个显式格式字符串所控制的表示时间的字符串。用法:datetime.strftime(format)importdatetimedt=datetime.dateti......