对于欧拉函数的求法最常用的有两方式
试除法比较简单，这里就不解释了。
这里主要介绍线性筛法求欧拉函数。
我们先了解什么是欧拉函数：
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;
}
文章浏览阅读289次。RF演进protocol 演进_nfc的演进
文章浏览阅读384次。wait 和notify 是实现线程之间的协同工作，必须结合synchronized使用，wait 释放锁，notify 不释放锁(但是此时会通知在等待的wait，该notify完全执行完毕，才真正释放锁)public class DemoThread18{ //原子类 private volatile List<String> list = new ArrayList..._wait 和 notify原理
文章浏览阅读601次。相信大部分 做ui的朋友 都非常痛恨一件事情 就是程序以及css和不同浏览器的兼容问题，我就奇怪了google你不好好的做你的搜索引擎，弄什么浏览器呀，本让现在 作东西考虑各个浏览器兼容 已经够累的，你还真会添乱。本来做你就做也无所谓，还花那么大力气推广，要不说你有钱，有了用户群，写东西就不得不考虑你了，大哥我们这些 闷头写程序的不容易，我们还要养家户口呢，你就别添乱了行不行。 _谷歌浏览器 我是人类
文章浏览阅读551次，点赞18次，收藏9次。前端演示咨询客服：
文章浏览阅读6.4k次，点赞7次，收藏29次。一、MAKO Vimba2.0安装教程1. 打开Vimba2.0安装软件，用户可到大恒官网下载最新驱动。2.选择选项Application Development和安装路径，注意：安装路径中不要存在空格。然后，点击Star，开始安装。 3.勾选Install Vimba Drivers，然后，点击Exit退出。4.接下来继续安装，勾选-选择“安装”，重复操作..._vimba viewer
文章浏览阅读3k次。UDP报文的处理入口是udp_rcv函数，该函数是在ip_local_deliver_finish函数中被调用的。1、udp_rcv函数int udp_rcv(struct sk_buff *skb){ return __udp4_lib_rcv(skb, &udp_table, IPPROTO_UDP);}2、__udp4_lib_rcv函数int __udp4_lib_rcv___udp4_lib_rcv
文章浏览阅读3.2k次。c# Restful_c#调用restful接口
文章浏览阅读1.8k次，点赞4次，收藏24次。HOG特征简介HOG 全称为 Histogram of Oriented Gradients ，即方向梯度的直方图。HOG 是由 Navneet Dalal & Bill Triggs 在 CVPR 2005发表的论文中提出来的，目的是为了更好的解决行人检测的问题。先来把这几个字拆开介绍，首先，梯度的概念和计算梯度的方法已经在前一篇文章中介绍了，方向梯度就是说梯度的方向我们也要利用上，..._hog特征识别行人 peopledetector=vision.peopledetector; i=imread(
文章浏览阅读2.8k次，点赞2次，收藏9次。上一篇文章中介绍了如何使用Spring Cloud搭建微服务，在本文中讲讲如何对微服务进行安全保护。在Spring Cloud中对应用进行安全保护通常使用Spring Security，这种方式集成起来非常简单而且很容易扩展现有的应用场景。在分布式环境中Spring Security使用Spring Session和Redis来共享会话。共享会话可以将在微服务网关中登录的用户验证信息传递到系统..._springboot微服务安全
文章浏览阅读961次。通过自学《碱基矿工》[http://mp.weixin.qq.com/mp/homepage?__biz=MzAxOTUxOTM0Nw==&hid=1&sn=d945cf61bd86e85724e146df42af5bcc&scene=18#wechat_redirect]下面分别介绍这两种格式FASTAFASTA常作为存储有顺序的序列数据的文件后缀，包括我们常用的..._.fa.gz
文章浏览阅读1k次。centos安装mysql如果设置的密码太简单了会报错（ ERROR 1819 (HY000): Your password does not satisfy the current policy requirements）解决方案如下：登录mysql执行：第一个密码强度等级，第二个是密码长度设置为6位（如果你设置的是8位就不做修改）另外可以通过语句查看密码设置规则2 赋权所有远程ip都可以进行登录（如果未开放端口得需要去腾讯云或者阿里云官网实例防火墙与策略开启端口，mysql默认的_centos 查看 mysql 远程连接
文章浏览阅读299次。本人使用的环境是CentOS-6.4-x86_64-bin-DVD1.rar,nginx-1.6.2.tar.gz,keepalived-1.2.18.tar.gz。三台机器ip：192.168.1.123，192.168.1.124。同时关闭两台虚拟机的防火墙：chkconfig iptables off(永久关闭防火墙)..._linux搭建nginx+keepalived