1 … n тоонуудаас n-тэй харилцан анхных нь хэд байгааг буюу φ(n)-ийг анхны хуваагчаар нь олдог арга.

IntermediateХугацаа: O(√n)Санах ой: O(1)

Эхлээд жижиг бодлого

n = 12. 1-ээс 12 хүртэлх тоонуудаас 12-той ерөнхий хуваагчгүй нь 1, 5, 7, 11. Тиймээс φ(12) = 4.

Томьёогоор: 12-ын анхны хуваагчид 2, 3. 12 × (1 − 1/2) × (1 − 1/3) = 12 × 1/2 × 2/3 = 4.

Энгийн аргаас санаа руу

Энгийн арга бол 1-ээс n хүртэлх тоо бүрийн GCD-г n-тэй бодох. Нэг n-д O(n log n), n = 10⁹ бол хэтэрхий удаан.

Харин φ(n) зөвхөн n-ий анхны хуваагчдаас хамаарна. p-д хуваагддаг тоонууд нийт тоонуудын 1/p хэсэг. Тэдгээрийг хасахад n × (1 − 1/p) үлдэнэ. Анхны хуваагч бүрт үүнийг давтана. Анхны хуваагчдыг √n хүртэл хайхад хангалттай.

Нэр томьёо ба тэмдэглэгээ

φ(n)
1-ээс n хүртэлх тоонуудын n-тэй харилцан анхных нь хэд вэ.
харилцан анхны
GCD нь 1. Жишээ нь 8 ба 15.
res
Хариу. Эхэндээ n, анхны хуваагч бүрт res -= res / p.
m
n-ий анхны хуваагчдыг хувааж арилгасаар үлдсэн хэсэг.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
n = 36res = 36m = 36
n-ий анхны хуваагчид
хоосон

φ(36) нь 1-ээс 36 хүртэлх тоонуудаас 36-тай ерөнхий хуваагчгүй (GCD = 1) хэдэн тоо байгааг заана. 36-гийн анхны хуваагч p бүрийн үржвэрүүдийг зурж хасна. Зурагдаагүй үлдсэн нүдний тоо нь хариу.

Алхам 1 / 9
Хурд
  • Шалгаж буй p
  • Анхны хуваагч
  • Сая зурсан
  • n-тэй ерөнхий хуваагчтай
  • Харилцан анхны
Слайд 1 / 6

φ(n) гэж юу вэ?

1-ээс 36 хүртэлх тоонуудын хэд нь 36-тай ерөнхий хуваагчгүй вэ? Энэ тоог φ(36) гэж тэмдэглэнэ. Нэг бүрчлэн GCD бодолгүй, 36-гийн анхны хуваагчаар хурдан олъё.

euler-totient.cpp
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
cin >> n;
int res = n, m = n;
for (int p = 2; p * p <= m; p++) {
if (m % p == 0) {
while (m % p == 0) m /= p;
res -= res / p;
}
}
if (m > 1) {
res -= res / m;
}
cout << res << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

φ(n)-ийг олно. Euler-ийн теорем, mod дахь зэрэг, бутархай тоолох бодлогод хэрэглэнэ.

Яаж ажилладаг вэ?

1. res = n. p = 2-оос эхлэн p × p ≤ m байх хооронд анхны хуваагч хайна. 2. p хуваагч бол m-ийг p-д хуваагдахаа болитол хуваана. 3. p-гийн үржвэрүүдийг хасна: res -= res / p. 4. Эцэст нь m > 1 үлдсэн бол энэ нь том анхны хуваагч: res -= res / m. Томьёо: φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × … Оролт: n. φ(n)-ийг хэвлэнэ.

Яагаад зөв, хэр хурдан бэ?

res нь үргэлж олдсон анхны хуваагч бүрт хуваагддаг. Тиймээс res / p бүхэл тоо бөгөөд res -= res / p нь яг res × (1 − 1/p). m-ийг p-д бүрэн хуваадаг тул нийлмэл p хэзээ ч хуваагч болж гарч ирэхгүй. Loop дууссаны дараа m > 1 бол энэ нь √n-ээс их ганц анхны хуваагч, түүнийг тусад нь тооцно.

Loop p × p ≤ m хүртэл явдаг тул O(√n). n = 10⁹ бол 31 623-аас хэтрэхгүй алхам.

Түгээмэл алдаа

  • res = res * (1 - 1 / p) гэж бичих. Бүхэл хуваалтаар 1 / p = 0 болж хариу буруу. res -= res / p гэж бич.
  • Loop-ын дараах if (m > 1) шалгалтыг мартах. n = 14 бол 6-гийн оронд 7 гэж хариулна.
  • m-ийг p-д бүрэн хуваахгүй байх. Тэгвэл 4 шиг нийлмэл тоо хуваагч болж гарч ирнэ.

Хязгаарын тохиолдол

  • n = 1: loop ажиллахгүй, m = 1, хариу 1.
  • n анхны тоо: loop-д хуваагч олдохгүй, m = n үлдэж, хариу n − 1.
  • n нь анхны тооны зэрэг, жишээ нь 32: ганц анхны хуваагч 2, хариу 16.

Өөрийгөө шалга

  1. φ(13) хэд вэ?

    Хариу харах

    12. 13 анхны тул 1-ээс 12 хүртэлх бүх тоо харилцан анхны.

  2. φ(100) хэд вэ?

    Хариу харах

    40. 100 × 1/2 × 4/5 = 40.

  3. φ(1) хэд вэ?

    Хариу харах

    1. Кодонд loop ажиллахгүй, res = 1 хэвээр.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.φ(60)-ийг гараар бод.

    Hint харах

    60 = 2² × 3 × 5.

    Хариу ба тайлбар

    60 × 1/2 × 2/3 × 4/5 = 16.

  2. 2.1-ээс n хүртэлх бүх тооны φ-гийн нийлбэрийг ол. n = 5 бол хэд вэ?

    Hint харах

    Тоо бүрт кодыг дуудаж болно, эсвэл sieve хэлбэрээр бүгдийг нэг дор бод.

    Хариу ба тайлбар

    1 + 1 + 2 + 2 + 4 = 10. Sieve хувилбар: phi[i] = i, анхны p бүрт түүний үржвэр бүрийг phi[j] -= phi[j] / p болгоно.

  3. 3.3¹⁰⁰ mod 10-ыг Euler-ийн теорем ашиглан ол.

    Hint харах

    GCD(a, m) = 1 бол a^φ(m) mod m = 1. φ(10) хэд вэ?

    Хариу ба тайлбар

    φ(10) = 4, 100 нь 4-т хуваагдана. Тиймээс 3¹⁰⁰ = (3⁴)²⁵, хариу 1.

Жишээ

Оролт

36

Гаралт

12