对于欧拉函数的求法最常用的有两方式
试除法比较简单，这里就不解释了。
这里主要介绍线性筛法求欧拉函数。
我们先了解什么是欧拉函数：
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;
}
文章浏览阅读460次。DescriptionSolution首先我们可以知道两个性质：1、路径u-v和路径v-w可以合并为路径u-w；2、路径u1-v1加路径u2-v2和路径u1-v2加路径u2-v1是等价的(就是起始点和终点可以互换) 那么知道这些性质之后就很好做了。我们只用知道每个点多少次做起点和多少次做终点。 我们设f[i]表示满足i子树的需求i上的值要是多少。 那么枚举i的所有儿子，判断a[i]-f[i]，_gdoi2018省选模拟树
文章浏览阅读2.8k次，点赞4次，收藏28次。我们进行简单的运算即可实现倒序。_字符串替换pta
文章浏览阅读4k次，点赞5次，收藏22次。traceroute 180.101.50.188————————测试到180.101.50.188有多少个网关。vim /etc/sysconfig/static-routes——————————修改。netstat -antp | grep 22———————查看端口号22的相关信息。systemctl restart network————————————重启。systemctl restart network————————重新启动。_linux如何开启网络连接
文章浏览阅读4w次，点赞23次，收藏6次。本人pr小白，今天编辑视频时候遇到了问题，也解决了，所以分享记录一下。问题一视频下面原来有字幕的，可是导入的视频变大了，现在看不到了怎么办？还有就是，频导入之后画质好像变糊了又是为什么？解决：将箭头放到要编辑的视频那里，右击，然后点击设为帧大小这样完整的视频就出来了。问题二如果视频模糊，就是序列设置的不对 要先新建序列一般的都是1920×1080本人博客：https://blog.csdn.net/weixin_46654114本人b站求关注：https://space.bi_avi视频到pr里会放大
文章浏览阅读1.8k次。注：key可以不用引号，value使用单引号,但key中存在_或-等一些特殊字符时，需要加上引号，避免出错。注：key可以不用引号，value也不用引号,但key中存在_或-等一些特殊字符时，需要加上引号，避免出错。注：使用@Value注解获取，apollo中未配置时默认为null。注：使用@Value注解获取，apollo中未配置时默认为null。2.apollo中的Map配置。1.apollo中的Map配置。注：使用逗号分隔，不用引号。..._apollo list
文章浏览阅读4.4k次，点赞22次，收藏12次。本文来自：中国科学技术大学公众号北京时间12月4日国际顶尖杂志《Science》刊发了中国科学技术大学潘建伟、陆朝阳等组成的研究团队的一项重磅研究成果让我们一起来看看吧！中国科学家实现“量子计算优越性”里程碑中国科学技术大学潘建伟、陆朝阳等组成的研究团队与中科院上海微系统所、国家并行计算机工程技术研究中心合作，构建了76个光子100个模式的量子计算原型机“九章”，实现了具有实用前景的“高斯玻色取样”任务的快速求解。根据现有理论该量子计算系统处理高斯玻色取样的速度比目前最快的超级计算机快一百万._中国科学院比马普所强
文章浏览阅读2k次。关于Vertectorization哪些是正确的（ ）相对于其他编程模型，sql在大数据领域有哪些好处（ ）哪些部分适合做codegen（ ）关于内存计算描述不正确的有（ ）_vertectorization
文章浏览阅读306次。百度找到了某论坛高人写的java(具体论坛记不清了)，直接用来调用，再次非常感谢，基本上实现了我的需求package MD5;import java.util.Scanner;public class ChineseToPinYin {/*** 汉字转拼音缩写** @param str* 要转换的汉字字符串* @return String 拼音缩写*/public Strin..._java生成拼音码
文章浏览阅读93次。/* 堆排序 */#include <iostream>using namespace std;int *data;void Sift(int k,int last){ int i,j,temp; i=k;j=2*i+1; while (j<=last) { if(j<last&&data[j]<data[j+1]) j++; if(data[i]>data[j]) _数据结构堆排序c++
文章浏览阅读952次。再查查资料，有没有DEBIAN问题解答中心呢？_debian 无法打开命令行窗口
文章浏览阅读2.3k次，点赞3次，收藏10次。2345王牌输入法的卸载输入法卸载了也还有2345这个流氓输入法，研究3个小时找到了2345输入法在语言栏的根源所在，希望能帮到你windows键加R键打开运行，输入regedit 然后ctrl+F键 搜索下面路径，打开后就会看见语言栏里的输入法了，直接删除加粗这个文件夹，就删除了HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\CTF\TIP{0055AAB0-EACB-46DB-9BB4-1B97FC046D02}\LanguageProfile\0x00000804\ _89e1d5c2-a068-44b6-b820-f8406c8a4706
文章浏览阅读2.2k次。1、开机启动system/core/init/main.cppint main(int argc, char** argv) {#if __has_feature(address_sanitizer) __asan_set_error_report_callback(AsanReportCallback);#endif if (!strcmp(basename(argv[0]), "ueventd")) { return ueventd_main(argc,._android setenforce