欧拉函数
发布日期:2021-07-27 13:45:08 浏览次数:1 分类:技术文章

本文共 844 字,大约阅读时间需要 2 分钟。

线性筛O(n)时间复杂度内筛出maxn内欧拉函数值

类似于欧拉筛法,详情参见

#include
#include
using namespace std;const int maxn=1e5;int n,m[maxn+1],pri[maxn+1],phi[maxn+1];//m[i]是i的最小素因数,p是素数,pt是素数个数int euler(){ int cnt=0; phi[1]=1; for(int i=2;i<=maxn;i++) { if(!m[i]) { pri[++cnt]=m[i]=i; phi[i]=i-1; } for(int j=1;j<=cnt&&pri[j]*i<=maxn;j++) { m[i*pri[j]]=pri[j]; if(m[i]==pri[j])//为了保证以后的数不被再筛,要break(参见欧拉筛法) { phi[i*pri[j]]=phi[i]*pri[j]; //这里的phi[k]与phi[i]后面的∏(p[i]-1)/p[i]都一样(m[i]==p[j])只差一个p[j],就可以保证∏(p[i]-1)/p[i]前面也一样了 break; } else//积性函数 phi[i*pri[j]]=phi[i]*phi[pri[j]]; } }}int main(){ euler(); scanf("%d",&n); printf("%d\n",phi[n]); return 0;}

转载地址:https://blog.csdn.net/Rlt1296/article/details/51882517 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:HDU 2824 The Euler function
下一篇:素数筛法

发表评论

最新留言

初次前来,多多关照!
[***.217.46.12]2024年03月16日 03时52分08秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

C语言极坐标转直角坐标,C语言实现直角坐标转换为极坐标的方法 2019-04-21
16F877A和24C02通信汇编语言,PIC16f877A读写24c02程序 2019-04-21
用c语言编写小于n的所有素数,关于求N以内素数的一点小问题(N小于一亿) 2019-04-21
华为100万部鸿蒙,2019年Q4发布 华为100万部鸿蒙OS手机已开测 2019-04-21
android+大富翁+局域网,【图片】大富翁6局域网(LAN)多人联机教程(求精)_大富翁吧_百度贴吧... 2019-04-21
rn webview加载本地静态html,React Native - Webview 加载本地文件 2019-04-21
dax powerbi 生成表函数_Power BI |DAX函数のCALCULATETABLE、CALENDAR函数以及相关表生成函数... 2019-04-21
编程之类的文案_如何锻炼写文案的能力? 2019-04-21
vscode 不能使用中文输入法_vscode中vim插件设置 2019-04-21
当集合a为空集时a的取值范围_1.1.2 集合间的基本关系 2019-04-21
vue 可合并表格组件_Vue实战046:详解Mixins混入使用和注意事项 2019-04-21
python包怎么做双重差分did分析_多变量相关性分析(一个因变量与多个自变量) 2019-04-21
fi sap 凭证冲销 稅_SAP中的成本要素 2019-04-21
mysql幻读是什么意思_MySQL中的幻读,你真的理解吗? 2019-04-21
mysql执行计划中性能最差的是_MySQL性能优化(七):MySQL执行计划,真的很重要,来一起学习吧... 2019-04-21
易语言执行mysql命令_易语言通过“打开”命令操作数据库 2019-04-21
mysql slave 1062_mysql主从同步slave错误1062 2019-04-21
mysql构造器_MySQL行构造器表达式优化(Row Constructor Expression) 2019-04-21
2008日志清理 server sql_SQL Server 2008 清除日志 2019-04-21
mac mysql root 权限_Mac平台重新设置MySQL的root密码 2019-04-21