线性筛求欧拉函数-程序员宅基地

技术标签：算法学习 c++ 数学知识

对于欧拉函数的求法最常用的有两方式

试除法
线性筛法

试除法比较简单，这里就不解释了。

这里主要介绍线性筛法求欧拉函数。

我们先了解什么是欧拉函数：
$\sim N 中与 N 互质的数的个数被称为欧拉函数，记为\varphi(N)。$
对于一个整数 $N$ :

如果 $N$ 为素数的话：那么在小于等于N中，与 $N$ 互质的为 $\sim N-1$ ，就是 $N - 1$ ；
如果 $N$ 不为素数的话：那么我们可以用到一个积性函数定理 $f (n * m) = f (n) * f (m)$ ，那么就可以进行拆分计算。

那么我们就可以用素数筛的板子，然后进行加入一些语句就可以实现线性筛求欧拉函数。
先说区别区别点吧：
第一个：

if(!used[i])
 {
    
     phis[i] = i-1;
     primes[++cnt] = i;
 }

第一个可以由上述 1 可以解释出来。
第二个：

if(i % primes[j] == 0)
{
    
    phis[i * primes[j]] = primes[j] * phis[i];
    break;
}
phis[i * primes[j]] = (primes[j] - 1) * phis[i];

这里就是素数筛的板子，然后加了点东西。

第一个语句中：如果 $\mod primes[j]$ 为 0 的话，那么 $i$ 包括了 $m (m = i * p r im es [j])$ 的所有的质因子，那么 $\varphi(m) = primes[j] * \varphi(i)$ 。
证明：因为 $i$ 包括了 $m$ 的所有质因子，所以 $\varphi(m) = m * \prod_{k=1}^{s}(1-\frac{1}{p_k}) = primes[j] * i * \prod_{k=1}^{s}(1-\frac{1}{p_k}) = primes[j] * \varphi(i)$ 。
例如： $\varphi(28) = 2 * \varphi(14)$ 。
第二个语句中，如果 $\mod primes[j]$ 不为 0 ，那么两个数互质，又通过上面的性质1得到 $\varphi(m) = (primes[j]-1) * \varphi(i)$ 。

下面就是代码环节，结合素数筛更好理解。
对应例题：
洛谷：T349752 筛法求欧拉函数

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

const int N = 1e6 + 5;

int primes[N],used[N],cnt; // 素数筛的变量
int phis[N];  // 定义的是每个整数对应的欧拉值是多少。
void phi(int x)
{
    
    cnt = 0;
    phis[1] = 1;
    for(int i = 2; i <= x; i++)
    {
    
        if(!used[i])
        {
    
            phis[i] = i-1;
            primes[++cnt] = i;
        }
        for(int j = 1; i * primes[j] <= x; j++)
        {
    
            used[i * primes[j]] = true;
            if(i % primes[j] == 0)
            {
    
                phis[i * primes[j]] = primes[j] * phis[i];
                break;
            }
            phis[i * primes[j]] = (primes[j] - 1) * phis[i];
        }
    }
}

void solve()
{
    
    int n;
    cin >> n;
    phi(n);
    long long res = 0;
    for(int i =1 ; i <= n; i++)
    {
    
        res += phis[i];
    }
    cout << res << endl;
}

signed main ()
{
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
//    cin >> T;
    while(T--)
        solve();
    return 0;
}

本文链接：https://blog.csdn.net/iwant_/article/details/132367449

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

职称计算机在线模拟考试,2017职称计算机考试Windows模拟试题-程序员宅基地

文章浏览阅读256次。2017职称计算机考试Windows模拟试题习题的练习有利于知识点的复习，下面是小编给大家提供的职称计算机考试Windows模拟试题，大家可以参考练习，更多习题练习请关注应届毕业生考试网。1 Windows"回收站"中不可能有。答案： DA 文件夹B 硬盘中的文件C 快捷方式D 软盘中的文件2 在windows资源管理器中，当前文件夹为D;\考试，选择其中的文件A.DOC，按住Shift键，用鼠..._在windows10操作环境下，文件命名错误的是

语音识别ASR背后的原理_asr算法识别静音是怎恶魔做到的-程序员宅基地

文章浏览阅读967次，点赞10次，收藏19次。语音识别技术（Automatic Speech Recognition）是一种将人的语音转换为文本的技术。_asr算法识别静音是怎恶魔做到的

第五章微服务框架-Spring Boot、Spring Cloud_springboot微服务-程序员宅基地

文章浏览阅读526次。随着动态语言的流行(Ruby、Groovy、 Scala、 Node.js) ，Java的开发显得格外的笨重繁多的配置、低下的开发效率、复杂的部署流程以及第三方技术集成难度大。在上述环境下，Spring Boot应运而生。它使用“习惯优于配置”(项目中存在大量的配置，此外还内置了一个习惯性的配置 ,让你无需手动进行配置)的理念让你的项目快速的运行起来。_springboot微服务

如何查看数据包路由和转发情况_看发送的数据包的转发过程-程序员宅基地

文章浏览阅读1.7k次。tcpdump是一个强大的网络分析工具，可以捕获和分析网络流量。它可以应用于任何网络接口，包括veth、bridge等设备。例如，你可以使用以下命令来捕获在某个veth设备上的流量：其中vethXXX是你想要观察的veth设备的名称。: ip命令是一个多功能的网络配置工具。你可以使用它来查看网络设备、路由表、ARP表等信息。例如，你可以使用以下命令来查看veth设备的状态：你还可以使用以下命令来查看路由表：: netstat命令可以显示网络连接、路由表、接口统计等信息。_看发送的数据包的转发过程

计算两个经纬度点之间的距离_getdistance求经纬度之间的距离-程序员宅基地

文章浏览阅读1.2k次。计算经纬度点之间距离的算法 getDistance(lat1, lng1, lat2, lng2) { const radLat1 = lat1 * Math.PI / 180.0; const radLat2 = lat2 * Math.PI / 180.0; const a = radLat1 - radLat2; con..._getdistance求经纬度之间的距离

Unity + Grpc + protobuf + C# 使用流程详解_unity grpc-程序员宅基地

文章浏览阅读3.7k次，点赞11次，收藏30次。最近公司的一个unity项目要把通信方式从Photon替换成grpc，正好系统学一下grpc,以下是我的学习心得。本篇博客系统详细地介绍了unity使用grpc通信的全部要点，希望可以帮助到大家。奥利给！详解目录一、本篇博客知识点简介二、资源及工具的下载地址1、protocolBuffer各个版本2、GRPC3、grpc_unity_package.2.27.0-dev4、.NET Core SDK 2.1及以上三、C#使用Grpc方法流程1、新建项目2、定义服务3、使用GRPC.Tools自动生成.c_unity grpc