当前位置: 首页 > news >正文

数学学习总结

andycode 巨神会莫比乌斯反演!于是我开始严肃学习数学。

这里主要是重要结论。

欧拉函数(\(\phi\)

定义 & 性质

欧拉函数 \(\phi(x)\) 表示不大于 \(x\) 的正整数中与 \(x\) 互质的数的数量。

那质数 \(x\)\(\phi\) 值就是 \(x-1\)

欧拉函数是积性函数,对于 \(x,y\in \N_+\)\(\gcd(x,y)=1\)\(\phi(xy)=\phi(x)\times \phi(y)\)

基于此可以用欧拉筛线性求 \(\phi\)

欧拉筛很好用,可以搭配莫比乌斯反演和数论分块一起食用。

求法

线性求 $\N_+$ 范围内所有数的 $\phi$
void get_phi() {phi[1] = 1; for(int i = 2; i <= N; i++) {if(!npr[i]) prime[++tot] = i, phi[i] = i - 1, vis[i] = i; for(int j = 1; j <= tot && prime[j] * i <= n; j++) {npr[i * prime[j]] = 1; vis[i * prime[j]] = prime[j]; if(i % prime[j] == 0) {phi[i * prime[j]] = phi[i] * prime[j]; break; } phi[i * prime[j]] = phi[i] * phi[prime[j]]; }} 
}

如果只求一个数的 \(\phi\) 有更好的求法,需要用到 Pollard-Rho 算法。

http://www.hskmm.com/?act=detail&tid=22567

相关文章:

  • VMware Aria Suite Lifecycle 8.18 Patch 5 发布,新增功能概览
  • P3977 [TJOI2015] 棋盘题解
  • 03. 基本元素
  • 基础整理01:Bode图、PM、GM、极点零点 - 教程
  • [已解决]CUDA error: CUBLAS_STATUS_EXECUTION_FAILED when calling cublasSgemmStridedBatched
  • VMware vCenter Server 7.0U3w 发布 - 集中管理 vSphere 环境
  • VMware Aria Operations 8.18.5 发布,新增功能概览
  • VMware Aria Operations for Logs 8.18.5 发布,新增功能概览
  • 专题:2025医药行业数智赋能与AI应用全景研究报告|附200+份报告PDF、数据仪表盘汇总下载
  • 喵之勇者败北录
  • Windows 作为 Ansible 节点的完整部署流程(含 Docker 部署 Ansible) - 实践
  • 软工
  • 10.1考试T4(swap)题解
  • 基本分段存储管理方式
  • 专题:2025零售数字化与即时零售竞争洞察报告|附130+份报告PDF、数据仪表盘汇总下载
  • 2025/10/1图论
  • 详细介绍:Python 豆瓣TOP250 爬虫类讲解
  • springboot用jar启动能访问,但是打成war,部署到tomcat却访问不到 - 详解
  • 用AirPods控制的创新iPhone游戏:RidePods技术解析
  • oppoR9m电话号码盘对应工程模式
  • 常量
  • Index of /ubuntu-releases/25.10/
  • P10364 [PA 2024] Dzielniki 题解
  • 20251001 之所思 - 人生如梦
  • 25普及联考day6爆炸记
  • unity面向组合开发一:面向对象(OOP)与面向组合(EC)
  • 两级页表
  • 复健。(10月,OI)
  • 实用指南:自动驾驶中的传感器技术55——USS(1)
  • 市场交易反心理特征之三:日内假反转