本资源包含 1 个源码文件 支持在线预览，点击文件名即可查看
温馨提示：点击文件名或"查看源码"按钮可在线浏览源代码，支持语法高亮显示。
资源详细信息
Euler函数: m = p1^r1 * p2^r2 * …… * pn^rn ai >= 1 , 1 <= i <= n Euler函数： 定义：phi(m) 表示小于等 - 资源详细说明
Euler函数:
m = p1^r1 * p2^r2 * …… * pn^rn ai >= 1 , 1 <= i <= n
Euler函数：
定义：phi(m) 表示小于等于m并且与m互质的正整数的个数。
phi(m) = p1^(r1-1)*(p1-1) * p2^(r2-1)*(p2-1) * …… * pn^(rn-1)*(pn-1)
= m*(1 - 1/p1)*(1 - 1/p2)*……*(1 - 1/pn)
= p1^(r1-1)*p2^(r2-1)* …… * pn^(rn-1)*phi(p1*p2*……*pn)
定理：若(a , m) = 1 则有 a^phi(m) = 1 (mod m) 即a^phi(m) - 1 整出m
在实际代码中可以用类似素数筛法求出
for (i = 1 i < MAXN i++)
phi[i] = i
for (i = 2 i < MAXN i++)
if (phi[i] == i)
{
for (j = i j < MAXN j += i)
{
phi[j] /= i
phi[j] *= i - 1
}
}
容斥原理：定义phi(p) 为比p小的与p互素的数的个数
设n的素因子有p1, p2, p3, … pk
包含p1, p2…的个数为n/p1, n/p2…
包含p1*p2, p2*p3…的个数为n/(p1*p2)…
phi(n) = n - sigm_[i = 1](n/pi) + sigm_[i!=j](n/(pi*pj)) - …… +- n/(p1*p2……pk)
= n*(1 - 1/p1)*(1 - 1/p2)*……*(1 - 1/pk)
Euler函数: m = p1^r1 * p2^r2 * …… * pn^rn ai >= 1 , 1 <= i <= n Euler函数： 定义：phi(m) 表示小于等 - 源码文件列表
立即下载 Euler函数: m = p1^r1 * p2^r2 *
提示：下载后请用压缩软件解压，推荐使用 WinRAR 或 7-Zip
下载说明与使用指南
下载说明
- 本资源需消耗 2积分
- 24小时内重复下载不扣分
- 支持断点续传功能
- 资源永久有效可用
使用说明
- 下载后使用解压软件解压
- 推荐使用 WinRAR 或 7-Zip
- 如有密码请查看资源说明
- 解压后即可正常使用
积分获取方式
- 上传优质资源获得积分
- 每日签到免费领取积分
- 邀请好友注册获得奖励
- 查看详情 →