对于欧拉函数的求法最常用的有两方式
试除法比较简单，这里就不解释了。
这里主要介绍线性筛法求欧拉函数。
我们先了解什么是欧拉函数：
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;
}
文章浏览阅读2.2k次。本文采用CenOS 6 32位，JDK1.7进行编译 （1）安装编译库yum install cmake lzo-devel zlib-devel gcc gcc-c++ autoconf automake libtool ncurses-devel openssl-devel libXtst（2）安装mavenwget http://repos.fedorapeople.org/repos/dc_32位linux系统 编译hadoop
文章浏览阅读422次。BIND(Berkeley internet Name Daemon)也叫做NAMED，是现今互联网上使用最为广泛的DNS 服务器程序,本项目旨在更简单的维护我们内部的dns系统。环境：数据库: mysql5.6应用: bind-9.11.2环境: python3.８ , django30x01 安装数据库bash sql 建库语句use mysqlcreate database bind9; -..._使用web管理bind
文章浏览阅读282次。对于Java程序员来说，在虚拟机自动内存管理机制的帮助下，不再需要为每一个new操作去写配对的delete/free代码，不容易出现内存泄漏和内存溢出问题。不过，一旦出现内存泄漏和溢出方面的问题，如果不了解虚拟机是怎样使用内存的，那排查错误、修正问题将会成为一项异常艰难的工作。====从新生代出发-XX:+UseSerialGC 可互相激活新生代 ：Serial + 老年代： Serial Old 都是串行-XX:+UseParNewGC 可互相激活。_自动内存管理
文章浏览阅读529次。自己用原生javascript写的轮播图，分页器按钮Click点击与mouseover鼠标悬浮导航都支持。同时支持移动端触摸操作，自己写得感觉不足之处是图片滚动动画还不够平滑，再改改间隔与偏移量应该可以。函数接受参数应该改成对象更好，还没有改。感觉这次写的轮播图功能比较全面了哈。高手们请别笑话，不足请指正.上源码：先HTML：<!DOCTYPE html><html>&..._轮播图无缝链接带有小圆点且支持移动端触频滑动
文章浏览阅读339次。nginx - fastcgi - php - memcache 协同下的 请求的完整访问过程用户发送http请求报文给nginx服务器nginx会根据文件url和后缀来判断请求如果请求的是静态内容,nginx会将结果直接返回给用户； 如果请求的是动态内容,nginx会将请求交给 fastcgi客户端 ,通过 fastcgi_pass 将这个请求发送给 php-fpmphp-fpm 会将请求交给 wrapperwrapper 收到请求会生成新的线程调用 php动态程序解析服务器如果用
文章浏览阅读566次。一、actor对等调度。二、调度流程源码分析：thread_worker()、struct skynet_context、skynet_context_message_dispatch()、dispatch_message()。三、c语言到lua的调用过程分析。_actor公平调度
文章浏览阅读939次。该音乐播放器是我研究生开学前做出来的，花了我将近一个月的闲余时间，算是有模有样的了。现在算起来，应该有一年多没搞Android，所以现在看回以前的程序已经比较模糊了，整个工程的代码量还是比较庞大的，就不把代码贴出来了，感兴趣的可以自行下载代码。欢迎先体验我的App，来一场听觉与视觉的享受吧！视觉？？？？嗯，你没看错，安装后有惊喜，让你欲罢不能！（貌似有点夸张了）Apk下载地址：ht_登录即可查找最新的android应用、游戏、电影、音乐等精彩内容
文章浏览阅读1.1w次。 弄了一上午，终于把使用NetTcpBinding的双工通讯给弄清楚了，也算是对wcf有所掌握了，为了解决穿透防火墙的问题，所以决定尝试一下WsDualHttpBinding的双工通信，结果问题来了。。。 “无法注册 URL http://+:8735/Service/。另一应用程序已使用 HTTP.SYS 注册了该 URL。” 晕了一种个下午，百_无法注册应用去处理url地址
文章浏览阅读4.5k次，点赞5次，收藏52次。把手里积累了这么久的Python入门资料整理了一下，发现其实，有了这些，python入门真的不难，每天花点时间学，真的不会影响工作。下面一起来看看这些资料吧！可以学习python的地方 Python学习资料全部整理 Python可以做的事情 关于python的一些文章一、可以学习Python的地方1、实验楼：【Python基础+项目实战课程】https://www.lanqiao.cn/courses/13302、《笨办法学 Python》：这本书绝对是最简单的学习 Pyth.._python学习资料
文章浏览阅读1.2k次。yum 设置代理:vim /etc/yum.conf添加形如:proxy = http://user:pass@ip:portrpm 设置代理sudo rpm -Uvh https://xxxxx.rpm --httpproxy ip --httpport portreference: https://www.lightnetics.com/topic/3698/how-do-i-install-an-rpm-package-using-a-http-proxy..._linux 代理 rpm
文章浏览阅读3.1k次。加载一副位图到你的用户界面是很简单的，然而如果你需要马上加载一组更大的图片的话就会复杂的多.在许多情况下（例如有些组件像ListView,GridView以及ViewPager等），出现在屏幕上的图片总量，其中包括可能马上要滚动显示在屏幕上的那些图片，实际上是无限的. 那些通过回收即将移除屏幕的子视图的组件，内存使用得以保留.如果你不长期保持你对象的引用的话，垃圾收集器也会释放你所加载的位图内_android 每秒收到30张图片怎么处理
文章浏览阅读205次。我们公司开发的liveweb播放器是可支持H.264/H.265视频播放的流媒体播放器，性能稳定、播放流畅，可支持的视频流格式有RTSP、RTMP、HLS、FLV、WebRTC等，具备较高的可用性。支持h264、h265、AAC、G711等常见音视频格式。支持协议：RTSP、RTMP、HLS、HTTP-FLV、WebSocket-FLV、GB28181、HTTP-TS、WebSocket-TS、HTTP-fMP4、WebSocket-fMP4、MP4、WebRTC。对外提供HTTP API二次开发接口；_h5直接播放rtsp视频