对于欧拉函数的求法最常用的有两方式
试除法比较简单，这里就不解释了。
这里主要介绍线性筛法求欧拉函数。
我们先了解什么是欧拉函数：
1 ∼ N 中与 N 互质的数的个数被称为欧拉函数，记为 φ ( N ) 。 1 \sim N 中与 N 互质的数的个数被称为欧拉函数，记为\varphi(N)。 1∼N中与N互质的数的个数被称为欧拉函数，记为φ(N)。
对于一个整数 N N N:
那么我们就可以用素数筛的板子，然后进行加入一些语句就可以实现线性筛求欧拉函数。
先说区别区别点吧：
第一个：
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];
这里就是素数筛的板子，然后加了点东西。
下面就是代码环节，结合素数筛更好理解。
对应例题：
洛谷：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;
}
文章浏览阅读6k次，点赞3次，收藏15次。coursera-斯坦福-机器学习-吴恩达-第8周笔记-无监督学习coursera-斯坦福-机器学习-吴恩达-第8周笔记-无监督学习1聚类算法clutering1聚类算法简介2K-means21kmeans的目标函数22随机初始化23选择类别数3考试quiz维数约减 dimensionality reduction1数据压缩2数据可视化3维度约简-主成分分析法PCA1 PCA_pca反向压缩
文章浏览阅读5.2k次。一、插件安装Vundle是vim的一个插件管理器， 同时它本身也是vim的一个插件。插件管理器用于方便、快速的安装、删除、Vim更新插件。mkdir -p ~/.vim/bundlegit clone https://github.com/gmarik/Vundle.vim.git ~/.vim/bundle/Vundle.vim管理器安装完成后，vim ~/.vimrc命令创建.vimrc文件syntax on" tab宽度和缩进同样设置为4set tabstop=4set softta_bxbx.vim
文章浏览阅读7.2w次，点赞10次，收藏41次。本文适用于当前面临java.lang.ClassNotFoundException挑战的Java初学者。 它将为您提供此常见Java异常的概述，这是一个示例Java程序，可支持您的学习过程和解决策略。 如果您对与更高级的类加载器相关的问题感兴趣，我建议您复习有关java.lang.NoClassDefFoundError的文章系列，因为这些Java异常密切相关。 java.lang..._java.lang.classnotfoundexception:
文章浏览阅读1.2k次，点赞9次，收藏17次。不同的设备间建立连接往往需要通信，而串口通信是十分常用的一种。UART串口通信需要两根线来实现，一根用于串口发送，另外一更用于串口接收。UART串口发送或者接收过程中一帧数据包括1位起始位、8位数据位、1位停止位，为了提高数据的可靠性可以在停止位前加上1位奇偶校验位。串口通信虽然十分简单，但是在不同设备间发送的数据往往不止1个字节，往往需要多个字节组成的数据包。当我们按照数据包发送时我们需要考虑到以及，因此我们可以采用定义数据帧的方式解决上述两个问题。_一帧数据
文章浏览阅读1.4k次。1、Ctrl+←或→ ：跳过（左边或右边）一个光标相邻的单词或词组(标点符号相当于一个单词)。点击前光标位置：点击后光标位置：2、Shift+←或→：选中（左边或右边）一个光标相邻的字符。点击前显示：点击后显示： 3、Shift+Ctrl+←或→：选中（左边或右边）一个光标相邻的单词或词组(标点符号相当于一个单词)。点击前显示：点击后显示：4、Home/End：光标定位到当前行的行头/行尾。点击前:点击Home后:点击End后:5、Ctrl+Home/End：从光标所在位置直接回到当前文件开头/结尾。点击前_改代码快捷键
树是一个有n个有限数据元素的集合，其中有一个根节点，并且每个节点可以有多个子节点。树的深度与查找有关，可通过改进合并算法来减少树的深度，提高算法效率。
文章浏览阅读553次。编者按：在这个万物智联的时代，无论是在线网络购物，还是网络强国、数字中国建设，都离不开一张“看不见的网”——基础设施网络。2009年，首届双11每秒交易订单创建峰值400；2021年，双11每秒交易订单创建峰值58.3万，12年交易数字量猛增的背后，是阿里云在庞大分布式系统上计算和IO能力的飞跃，更离不开阿里云基础设施底层网络技术的支撑。图｜阿里云全球基础设施网络系统作为阿里云基础设施的重要组成部分，阿里云基础设施网络团队负责整个阿里云全球基础设施网络，包括大规模高性能数据中心网络，全球数据中心互联_阿里云网络基线理解
文章浏览阅读1.7k次。端口列表一览端口号码 / 层 名称 注释 1 tcpmux TCP 端口服务多路复用 5 rje 远程作业入口 7 echo Echo 服务 9 discard 用于连接测试的空服务 11 systat 用于列举连接了的端口的系统状态 13 daytime 给请求主机发送日期和时间 17 qotd 给连接了的主机发送每日格言 18 msp 消息发送协议 19 _怎么查看端口映射的是tcp还是udp
文章浏览阅读1.1w次。_微信小游戏 inneraudiocontext 数量限制
文章浏览阅读825次。一、概述1. JSBridge介绍什么是JSBridge主要是给 JavaScript 提供调用 Native 功能的接口，让混合开发中的前端部分可以方便地使用 Native 的功能（例如：地址位置、摄像头）。而且 JSBridge 的功能不止调用 Native 功能这么简单宽泛。实际上，JSBridge 就像其名称中的Bridge的意义一样，是 Native 和非 Native 之间的桥梁，它的核心是构建 Native 和非 Native 间消息通信的通道，而且这个通信的通道是双向的。双向通信的通_adnroid jsbridge 不安全的资源引用
文章浏览阅读2k次，点赞13次，收藏43次。OpenCV+Mediapipe+UDP+Unity挥手翻页_unity opencv 虚拟翻书
文章浏览阅读861次。vue前端运行别人的项目_前端项目运行不了