m анхны үед a × x mod m = 1 байх x-ийг Фермагийн бага теорем ба Fast Power ашиглан олно.

Advanced & LegendХугацаа: O(log m)Санах ой: O(1)

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

mod 7-д 2-ын урвуу тоог олъё: 2 · x mod 7 = 1 байх x.

Фермагийн бага теоремоор хариу нь 2⁵ mod 7. 2⁵ = 32, 32 = 4 × 7 + 4 тул x = 4. Шалгая: 2 · 4 = 8 = 7 + 1.

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

Энгийн арга бол x = 1, 2, …, m − 1 бүрийг туршиж үзэх. m = 10⁹ + 7 бол тэрбум алхам.

m анхны бол Фермагийн бага теорем: a^(m − 1) mod m = 1. Тэгэхээр a · a^(m − 2) mod m = 1, урвуу тоо нь a^(m − 2) mod m. Үүнийг Fast Power-оор log m алхамд бодно.

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

урвуу тоо a⁻¹
a · a⁻¹ mod m = 1 байх тоо. mod дээр хуваахын оронд үүгээр үржүүлнэ.
b = m − 2
Зэрэг. Битээр нь задалж Fast Power хийнэ.
res
Хариу, эхэндээ 1. b сондгой үед a-гээр үржинэ.
a
Алхам бүрт квадрат зэрэгт дэвшинэ: a, a², a⁴, a⁸, …
b = m − 2 = 9 (хоёртын)
1
8
0
4
0
2
1
1
a
3⁸
3⁴
3²
3
3¹
a = 3b = 9res = 1m = 11

3 × x mod 11 = 1 байх x-ийг хайна. Фермагийн бага теорем: m анхны бол a¹⁰ mod m = 1. Тэгэхээр a × a⁹ mod m = 1, хариу нь 3⁹ mod 11. Fast Power ашиглан бодъё.

Алхам 1 / 16
Хурд
  • Шалгаж буй бит
  • Хариунд орсон
  • Шинээр бодсон a
  • Алгассан бит
Слайд 1 / 5

mod дахь хуваах үйлдэл

mod дээр нэмэх, хасах, үржүүлэх амархан. Харин хуваах нь «урвуу тоогоор үржүүлэх» гэсэн үг. 3 × x mod 11 = 1 байх x хэд вэ?

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

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

mod дээр хуваах: a / b mod m = a × b⁻¹ mod m. C(n, k) mod p, магадлалын бодлогод зайлшгүй хэрэгтэй.

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

1. Фермагийн бага теорем: m анхны бөгөөд a нь m-д хуваагдахгүй бол a^(m − 1) mod m = 1. 2. Тэгэхээр a × a^(m − 2) mod m = 1, урвуу тоо нь a^(m − 2) mod m. 3. Fast Power: b = m − 2. b сондгой бол res = res × a % m. Дараа нь a = a × a % m, b /= 2. 4. m анхны биш бол Extended Euclid ашиглана. Оролт: a, m (анхны тоо). Урвуу тоог хэвлэнэ.

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

b-г хоёртын системээр бичвэл a^b нь a, a², a⁴, a⁸, … зэргүүдийн заримынх нь үржвэр болно: a⁹ = a⁸ · a¹. Loop-ын алхам бүрт a нь a^(2^k) байх ба b-гийн тухайн бит 1 бол res-д үржинэ. Тиймээс эцэст нь res = a^b mod m. Фермагийн теоремоор энэ нь урвуу тоо.

Алхмын тоо нь b-гийн битийн тоо: m = 10⁹ + 7 бол 30. Үржвэр бүрийг m-д хуваасан үлдэгдлээр хадгалдаг тул тоо томордоггүй.

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

  • m анхны биш үед Фермаг хэрэглэх. m = 8, a = 3 бол 3⁶ mod 8 = 1 гарна. Гэтэл 3 · 1 = 3, зөв хариу нь 3 (3 · 3 = 9). Анхны биш m-д Extended Euclid хэрэглэ.
  • res * a int-ээс хэтрэх. m ≈ 10⁹ бол үржвэр 10¹⁸ хүрнэ. long long ашигла.
  • a нь m-д хуваагддаг бол урвуу тоо байхгүй. Код 0 гэж хариулна, түүнийг шалгах хэрэгтэй.

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

  • a = 1: хариу 1.
  • a = m − 1: хариу нь өөрөө m − 1, учир нь (m − 1)² = m² − 2m + 1.
  • m = 3: b = 1, нэг алхамд хариу нь a өөрөө.

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

  1. mod 7-д 3-ын урвуу тоо хэд вэ?

    Хариу харах

    5. 3 · 5 = 15 = 2 · 7 + 1.

  2. mod 7-д 6-гийн урвуу тоо хэд вэ?

    Хариу харах

    6. 6 · 6 = 36 = 5 · 7 + 1.

  3. m = 10⁹ + 7 бол loop хэдэн удаа ажиллах вэ?

    Хариу харах

    30. m − 2 нь 30 оронтой хоёртын тоо.

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

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

  1. 1.mod 13-д 5-ын урвуу тоог Fast Power-оор гараар бод.

    Hint харах

    b = 11 = 8 + 2 + 1. 5² mod 13, 5⁴ mod 13-ыг эхлээд ол.

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

    5² ≡ 12, 5⁴ ≡ 1, 5⁸ ≡ 1. 5¹¹ = 5⁸ · 5² · 5 ≡ 1 · 12 · 5 = 60 ≡ 8. Шалгая: 5 · 8 = 40 = 3 · 13 + 1.

  2. 2.(10 / 4) mod 7-г ол.

    Hint харах

    Хуваахын оронд 4-ийн урвуугаар үржүүл.

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

    4-ийн урвуу нь 2 (4 · 2 = 8). 10 · 2 = 20, 20 mod 7 = 6. Шалгая: 6 · 4 = 24 ≡ 3, 10 ≡ 3.

  3. 3.1-ээс n хүртэлх бүх тооны урвуу тоог mod p-д O(n)-д ол.

    Hint харах

    p = (p / i) · i + p % i гэдгийг mod p-д бич.

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

    inv[1] = 1, inv[i] = (p - p / i) * inv[p % i] % p. p = 7 бол inv[1..6] = 1, 4, 5, 2, 3, 6.

Жишээ

Оролт

3 11

Гаралт

4