对于欧拉函数的求法最常用的有两方式
试除法比较简单，这里就不解释了。
这里主要介绍线性筛法求欧拉函数。
我们先了解什么是欧拉函数：
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;
}
文章浏览阅读4.6k次。此处我们使用的是AES的基础加密模式，即：电码本模式 ECBJAVA代码如下： //创建AES加密实例 SecretKeySpec skeySpec = new SecretKeySpec(keyBytes, "AES"); Cipher cip = Cipher.getInstance("AES/ECB/NoPadding");//算法/模式/补码方式 cip.init(C_botan c++ aes java 互通
文章浏览阅读2.5k次，点赞5次，收藏17次。2018年3月，我与张老师就这么在微信上聊了起来，起初我并没有写书的打算，我们之间只是通过讨论、交流的形式聊聊关于出书的方方面面。最终，敌不过张老师超强的专业能力、细致的解说与盛情相邀，我答应张老师写一本Linux系统运维的图书并由人邮出版。由此，我踏上了漫漫2年多的写书之路。为什么写这本书写书一方面是我对自己所学知识的查漏补缺过程，另一方面也可以向即将进入或已经入行的Linux系统运维同..._linux系统运维指南:从入门到企业实战 pdf
文章浏览阅读2k次，点赞6次，收藏5次。tf.reduce_sum()函数深度解析从矩阵，数组，数据存储的角度 解析axis参数的意义_tf.reduce_sum
文章浏览阅读9.8k次，点赞4次，收藏29次。adb获取app包名的方法_adb获取包名
文章浏览阅读913次，点赞16次，收藏10次。总之，要做好虾皮店铺，不仅需要明确的定位和优质的产品，还需要精心的运营和持续的改进。通过不断优化店铺形象、制定有效的营销策略、提供优质的客户服务以及加强供应链管理等手段，您将能够在激烈的竞争中脱颖而出，实现店铺的长足发展。1.稳定的网络环境是基石，它需要经过技术手段的洗礼，将电脑或手机的底层硬件参数伪装成国外数据，以躲避平台通过IP进行的深度检测。这种真实性高的评价能够帮助商家获得更多的信任和认可，从而提升产品的排名和流量的分配。您可以关注行业动态，学习先进的经营理念和技术，以提高店铺的运营水平。
文章浏览阅读5k次，点赞11次，收藏43次。统计检验_统计测试 cd diagrams
文章浏览阅读2.9k次，点赞3次，收藏37次。1. IIS1. PUT漏洞用户配置不当，exp:https://github.com/hackping/HTTPMLScan.git2. 短文件名猜解IIS的短文件名机制，可以暴力猜解短文件名，访问构造的某个存在的短文件名，会返回404，访问构造的某个不存在的短文件名，返回400。exp:https://github.com/WebBreacher/tilde_enum3.远程代码执行(CVE-2017-7269))**exp**:https://github.com/zcgonv_hrs中间件
文章浏览阅读368次。DB2支持以下两种类型的表空间： 1、 系统管理存储器表空间（SMS-SYSTEM MANAGED STORAGE） 2、 数据库管理存储器表空间（DMS-DATABASE MANAGED STORAGE） SMS、DMS用户表空间的特性对照 特性 ..._db2
文章浏览阅读84次。正在开发中的游戏有个全屏功能--可以在window桌面背景上运行，就像一些视频播放器在桌面背景上播放一样的，花了个上午整了个Demo放出来留个纪念。实现功能：显示图标，双击图标执行相应的程序，右击图标弹出该图标对应得菜单，点击非图标区则弹出桌面菜单。需要完整工程可以点此下载：DesktopWindow.rar。程序效果图如下：在这个程序里，定义了一个XShellItem..._模拟实现windows桌面效果
文章浏览阅读944次。https://www.byhy.net/tut/webdev/django/01/_byhy.net
文章浏览阅读5.8k次，点赞13次，收藏57次。业务场景介绍：H5移动端支持微信支付 [ 微信支付分为微信内支付（JSAPI支付官方API）和微信外支付（H5支付官方API）] && 支付宝支付 [手机网站支付转 APP 支付 官方API ]订单生成逻辑：前端请求后端提交订单，后端去和微信或者支付宝对接生成订单（后续支付都是这个逻辑进行的对接）一、移动端微信支付，vue中如何玩？在移动端微信支付分为微信内支付和微信外支付。1.在订单组件中选择支付方式之后在支付页面先去判断是否是在微信内：//判断是否微信 is__移动端支付宝微信支付vue项目怎么写
文章浏览阅读2k次，点赞5次，收藏9次。深度学习编译器主要为解决不同框架下训练的模型部署到指定的某些设备上时所遇到的一系列复杂的问题，即将各种深度学习训练框架的模型部署到各种硬件所面临的问题；_tvm编译器