b-г хоёртын битүүдэд нь задалж, aᵇ mod m-ийг ердөө log b алхамд олдог арга.

Pre-IntermediateХугацаа: O(log b)Санах ой: O(1)
HackerRank дээр бодох

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

2¹⁰ mod 1000 хэд вэ? 10 = 8 + 2 тул 2¹⁰ = 2⁸ · 2². 2-ыг дахин дахин квадрат болговол 2, 4, 16, 256 гарна.

2² = 4 ба 2⁸ = 256-г үржүүлбэл 1024, 1000-д хуваасан үлдэгдэл нь 24. Хариу 24. Ердөө 4 удаа давтлаа.

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

Энгийн арга: res-ийг a-гээр b удаа үржүүлнэ. b = 10⁹ бол тэрбум үржвэр, хэт удаан.

b-г хоёртын бичлэгээр задлая: 13 = 8 + 4 + 1. Тэгвэл a¹³ = a⁸ · a⁴ · a¹. a, a², a⁴, a⁸ гэх мэт зэргүүдийг өмнөхийг нь квадрат болгож гаргана. b-гийн бит нь 1 байгаа зэргүүдийг л res-д үржүүлнэ. Бит log₂ b орчим тул давталт ч мөн төдий.

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

res
Хариу. Эхэндээ 1.
b % 2
b-гийн хамгийн баруун бит. 1 бол тэр зэрэг хариунд орно.
a = a * a % m
Дараагийн бит рүү шилжихэд a квадрат болно: a, a², a⁴, a⁸, …
mod m
m-д хуваасан үлдэгдэл. Үржүүлэх бүрт авч, тоог бага байлгана.
b = 13 (хоёртын)
1
8
1
4
0
2
1
1
a
3⁸
3⁴
3²
3
3¹
a = 3b = 13res = 1m = 1000

3¹³ mod 1000 хэд вэ? b-г хоёртын бичлэгээр задална: 1101. 13 = 8 + 4 + 1.

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

Хурдан зэрэг

3¹³ гэдэг нь 13 ширхэг 3-ыг хооронд нь үржүүлсэн тоо. Хариу маш их болдог тул 1000-д хуваасан үлдэгдлийг нь олъё. 13 удаа үржүүлэхгүйгээр хурдан олох арга бий.

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

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

aᵇ mod m-ийг хурдан олох: b нь тэрбум байсан ч 30 орчим удаа л давтана. Хариуг 10⁹ + 7-д хуваасан үлдэгдлээр гаргадаг олимпиадын бодлогод байнга хэрэглэгдэнэ.

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

1. res = 1. 2. b сондгой (b % 2 = 1) бол res = res × a % m. 3. a = a × a % m: дараагийн битүүдэд a², a⁴, a⁸ … хэрэгтэй. 4. b = b / 2: хамгийн баруун битийг хаяна. 5. b = 0 болтол давтана. Хариу нь res. Оролт: нэг мөрөнд a b m.

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

k дахь давталтын эхэнд a нь анхны a-гийн 2^k зэрэг (mod m) байна. b-гийн k дахь бит 1 бол тэр зэргийг res-д үржүүлнэ. Бүх бит дуусахад res-д b-г бүрдүүлдэг зэргүүд л үржигдсэн байна: энэ нь яг aᵇ mod m.

Давталт бүрт b хоёр дахин багасна: log₂ b + 1 давталт, хугацаа O(log b). b = 10¹⁸ бол 60 давталт.

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

  • res * a нь int-ээс хэтэрнэ. m ≈ 10⁹ үед long long хэрэгтэй. Энэ код бүгдийг long long гэж зарласан.
  • a нь m-ээс их байж болно (жишээ нь 10¹⁸). Эхлээд a %= m хий, эс тэгвээс a * a нь long long-оос ч хэтэрнэ.
  • m = 1 үед хариу 0 байх ёстой. Гэтэл b = 0 бол код 1 хэвлэнэ. res = 1 % m гэж эхлүүлбэл зөв.
  • res = res * a % m мөрийг if дотор биш гадна бичих. Тэгвэл бүх битийг үржүүлж, буруу хариу гарна.

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

  • b = 0: loop ажиллахгүй, хариу 1.
  • a нь m-д хуваагддаг (жишээ нь a = 10, m = 5): b ≥ 1 бол хариу 0.
  • b = 1: ганц давталт, хариу a % m.
  • b нь 2-ын зэрэг (жишээ нь 1024): res-д ганц удаа л үржүүлнэ.

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

  1. 3¹³ mod 1000 хэд вэ?

    Хариу харах

    323. 3¹³ = 1 594 323.

  2. b = 1000 бол хэдэн удаа давтах вэ?

    Хариу харах

    10. 1000-ын хоёртын бичлэг 1111101000 нь 10 оронтой.

  3. Яагаад үржүүлэх бүрт % m авдаг вэ?

    Хариу харах

    Тоо хэт томорч long long-оос хэтрэхээс сэргийлнэ. Үлдэгдлүүдийг үржүүлээд үлдэгдэл авсан ч хариу өөрчлөгдөхгүй.

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

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

  1. 1.a = 2, b = 13, m = 1000 үед давталт бүрийн дараах b, a, res-ийн утгыг бич.

    Hint харах

    Эхлээд res = 1. b сондгой үед л res өөрчлөгдөнө.

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

    b = 6, a = 4, res = 2. b = 3, a = 16, res = 2. b = 1, a = 256, res = 32. b = 0, a = 536, res = 192. Хариу 192 (2¹³ = 8192).

  2. 2.Кодыг recursive function болгож бич.

    Hint харах

    aᵇ нь a^(b/2)-гийн квадрат. b сондгой бол дээр нь нэг a үржүүлнэ.

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

    long long pw(long long a, long long b, long long m) { if (b == 0) return 1 % m; long long h = pw(a, b / 2, m); h = h * h % m; return b % 2 ? h * a % m : h; }

  3. 3.p анхны тоо (жишээ нь 10⁹ + 7), a нь p-д хуваагддаггүй. a · x mod p = 1 байх x-ийг ол (modular inverse).

    Hint харах

    Фермагийн бага теорем: a^(p − 1) mod p = 1.

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

    x = a^(p − 2) mod p. Fast Power ашиглан O(log p) хугацаанд олно. Mod дээр хуваах үйлдлийг ингэж хийдэг.

Жишээ

Оролт

3 13 1000

Гаралт

323

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.