33DAI：导入1个版本

2026-05-20T18:12:11Z

导入1个版本

←上一版本		2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 16:50的版本
（没有差异）

33DAI：导入1个版本

2026-05-20T16:25:39Z

导入1个版本

←上一版本		2026年5月20日 (三) 16:25的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:22:29Z

批量导入三三文档

新页面

欧拉函数 <math>\varphi(n)</math> 表示 <math>1\sim n</math> 中与 <math>n</math> 互质的数的个数。

== 求单个欧拉函数 ==

<math>O(\sqrt{n})</math>

<math>\varphi(n)=n\times \prod_{p\mid n}\left(1-\frac{1}{p}\right)</math>

<syntaxhighlight lang="cpp">
long long phi(long long n)
{
long long ans = n;
for (long long i = 2; i * i <= n; i++)
if (n % i == 0)
{
ans = ans / i * (i - 1);
while (n % i == 0)
n /= i;
}
if (n > 1)
ans = ans / n * (n - 1);
return ans;
}
</syntaxhighlight>

== 线性筛求欧拉函数 ==

<math>O(n)</math>，同时求出 <math>1\sim n</math> 所有数的欧拉函数值。

<syntaxhighlight lang="cpp">
const int MAXN = 40000;
bool p[MAXN + 5];
int phi[MAXN + 5];
vector<int> pri;

void get_phi(int n)
{
for (int i = 1; i <= n; i++)
p[i] = true;
p[0] = p[1] = false;
phi[1] = 1;
for (int i = 2; i <= n; i++)
{
if (p[i])
{
pri.push_back(i);
phi[i] = i - 1;
}
for (int j = 0; j < pri.size(); j++)
{
if (1LL * i * pri[j] > n)
break;
p[i * pri[j]] = false;
if (i % pri[j] == 0)
{
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
else
phi[i * pri[j]] = phi[i] * (pri[j] - 1);
}
}
}
</syntaxhighlight>

== 欧拉函数性质 ==

- 若 <math>p</math> 是质数，<math>\varphi(p)=p-1</math>
- 若 <math>p</math> 是质数，<math>\varphi(p^k)=p^k-p^{k-1}</math>
- 若 <math>\gcd(a,b)=1</math>，则 <math>\varphi(ab)=\varphi(a)\times\varphi(b)</math>（积性函数）
- <math>\sum_{d\mid n}\varphi(d)=n</math>

== 欧拉定理 ==

若 <math>\gcd(a,m)=1</math>，则：

<math>a^{\varphi(m)}\equiv 1\pmod m</math>

当 <math>m</math> 为质数时就是费马小定理。

[[Category:数学相关]]
[[Category:三三文档]]

06-数学相关/03-欧拉函数 - 版本历史

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档