对于欧拉函数的求法最常用的有两方式
试除法比较简单，这里就不解释了。
这里主要介绍线性筛法求欧拉函数。
我们先了解什么是欧拉函数：
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;
}
文章浏览阅读1.1w次，点赞3次，收藏5次。转载请说明来源于"厦门SEO"本文地址：http://www.96096.cc/Article/160880.html常用办公软件 WPS Office是由金山软件股份有限公司开发的一款针对个人永久免费的办公软件，在我们的日常生活和工作中，WPS Office比起微软Microsoft Office来说在文字上的处理会更深入国人用户的人心，熟悉操作WPS的办公小技巧，能够更高效的提高我们的工作效率，今天小编要为大家分享的是WPS怎么自动生成目录？快来一起看看WPS自动生成目录的设置教程吧。_wps目录自动生成
文章浏览阅读7.4k次，点赞2次，收藏19次。web项目是指服务端部署在服务器上，客户端使用浏览器通过网络传输进行访问获取数据的项目。通常我们看见的应用页面网站等等都可以称之为web项目。 在web项目的开发中可分为web前端开发和web后端开发 web前端：即是客户端能看得见碰得着得东西。包括Web页面结构、页面样式外观以及Web层面得交互展现。 前端特点：页面视觉效果良好（客户第一）、Web页面交互流畅（..._web项目
文章浏览阅读5.6k次，点赞8次，收藏67次。java操作关于导入导出Excel的多种方式_java导出excel的三种方法
文章浏览阅读1.1w次，点赞10次，收藏21次。Windows path系统变量编辑_windows path
文章浏览阅读512次。第13章 源码编译13.2 Hadoop2.7.3源码编译13.2.1下载Hadoop源码包（1）到官网http://hadoop.apache.org/releases.html下载2.7.3的source源码包（2）解压缩tar -zxvf hadoop-2.7.3-src.tar.gz -C /opt1(3)打开解压目录下的BUILDING.txt,编译过程和需要的软件其实就是根据这个文档里..._hadoop2.7.3-src源码下载
文章浏览阅读1k次。Latex 语法_\latex
文章浏览阅读753次，点赞30次，收藏21次。在线绿色新鲜果蔬商店网站是指一个专门销售新鲜、绿色、有机水果和蔬菜的电子商务平台。这类网站旨在为消费者提供方便、快捷的购买渠道，同时确保他们能够购买到高质量、新鲜的产品。
文章浏览阅读1k次。最近写项目碰到一个bug 大概就是一个表格组件两个页面都会使用 组件中表格的某些列就用v-if控制了 表格的首尾列都用了fixed 然后就发生了bug 如下图 具体原因不明看过很多网上的办法 有在fixed的列绑定key的 也有使用doLayout()的 测了都没用 最后在一个前端交流群里一位大佬给出的办法 实测有效.el-table__header, .el-table__body, .el-table__footer { width: 100%; tab_element table fixed 样式异常
文章浏览阅读1.8w次，点赞39次，收藏98次。最近在学习C语言基础的时候，我注意到了在写代码时经常使用的 #include <stdio.h>。众所周知，这是引用头文件的操作，但对于它的深层次含义，我并没有更多的了解。所以今天就来让我们深入研究一下它的更多信息。include的意思是包含，它前面的 # 是预处理指令。#通常有三种功能：1. 宏定义 2 .文件包含 3.条件编译。例如#define定义的标识符常量，这就属于一种宏定义的用法。其他的用法，随着深入学习相信也都会接触到。<stdio.h>就是我们引用的头文件，相_include 含义
文章浏览阅读722次。telnet命令通常用来远程登录。telnet程序是基于TELNET协议的远程登录客户端程序。Telnet协议是TCP/IP协议族中的一员，是Internet远程登陆服务的标准协议和主要方式。它为用户提供了在本地计算机上完成远程主机工作的 能力。在终端使用者的电脑上使用telnet程序，用它连接到服务器。终端使用者可以在telnet程序中输入命令，这些命令会在服务器上运行，就像直接在服务器的控制台_telnet linux reboot
文章浏览阅读5k次。重建视觉外观是色调映射的终极目标。色调映射算法在降低高动态图像(HDR)范围的同时着力保护捕捉到的原始图像的外观。色调映射算子分两种策略，一种是全局的，另一种是局部的。1. 全局映射算子每一个像素点将会根据它的全图特征和亮度信息进行映射，不管其空间位置几何。全局算子一个比较典型的例子就是色调曲线。全局色调映射在处理12位(12-bit)深度的图像的时候是完全OK的，当图像的动态范围特别高的时候，那就不行了。这是因为所有的像素点都采取同一种方式进行处理，根本就没有管它是在较亮区域还是较暗区域。这样的话，._local tone mapping
文章浏览阅读86次。1.RadioButtonRadioButton被称作为单选框，通常都是以组的形式出现，可以在一组控件中选择一个。RadioButton的使用首先需要加入<RadioGroup/>，在这个组中，我们进行单选按钮的声明。 1 <RadioGroup 2 android:id="@+id/radioGroup" 3 an..._radiobutton和toggombutton