ACM 第十九天
2024-08-30 01:29:01
积性函数
积性函数线性筛,筛素数,u(n),欧拉函数:
vis[]=vis[]=,mu[]=,phi[]=;
for (RG int i=;i<=N;++i){
if (!vis[i]) mu[i]=-,phi[i]=i-,prime[++cnt]=i;
for (RG int j=,k=i*prime[j];j<=cnt && k<=N;++j,k=i*prime[j]){
vis[k]=;
if (!(i%prime[j])){ mu[k]=,phi[k]=phi[i]*prime[j]; break; }
else mu[k]=-mu[i],phi[k]=phi[i]*phi[prime[j]];
}
}
可以发现,线性筛分为3部分:
1.n本身是素数,这个根据积性函数的定义可得,很容易求。
2.i%prime[j]!=0,这个也是根据积性函数的性质可得。f(a)f(b)=f(a
3.i%prime[j]==0,可能需要找规律。据ljh2000神犇的说法,可以用2,4,8或3,9,27这些数来找。
μ(n),ϕ
最新文章
- [LeetCode] Edit Distance 编辑距离
- Git Stash紧急处理问题,需要切分支
- 【Java】正则表达式
- 【转】Alchemy的使用和多项式批量计算的优化
- Uncaught exception &#39;PDOException&#39; with message &#39;SQLSTATE[HY000] [2002] No such file or directory&#39;
- Android基础
- springmvc注解配置
- 二、Spring——AoP
- HDU4456-Crowd(坐标旋转+二位树状数组+离散化)
- ZOJ3261 Connections in Galaxy War 并查集
- kickstrt脚本for cobbler基于system-config-kickstart配置
- Swift开发必备技巧:内存管理、weak和unowned
- .Net 缓存依赖详解
- JAVA 异常 throw 与 throws
- linux下安装redis和phpredis扩展
- 编写python程序和运行.py文件的方法步骤
- C# 使用ffmpeg视频截图
- 【CAS单点登录视频教程】 第05集 -- CAS服务器安装
- C++ Qt多线程 TcpSocket服务器实例
- ActiveStorage. 英文书Learnrails5.2的案例,看如何放到云上。