Юм хийхгүй байсан ч хугацаа өнгөрдөг юм байна. Дахиад a^b%p буюу a тооны b зэргийг p гэсэн тоонд хуваахад гарах үлдэгдлийг олцгооё(p нь анхны тоо). Өмнө нь бид a, b <= 10^13 гэсэн тохиолдолд бодсон байгаа. Энэ удаад үүнийгээ өргөтгөн a, b гэсэн хоёр тооны оронгийн тоо нь 10^6-с бага буюу тэнцүү тохиолдолд бодоцгооё(бодъё гэдэг үг бичих гэж байсан ч яаж бичих дээр эргэлзсэн ба p long long төрлийх). fermat -н бага теоремоор (a^(p-1))%p = 1. Үүнийг ашиглахад энэхүү бодлого маш амархан болж байгаа. (a^b)%p = ((a%p)^b)%p тул эхлээд a тоог p-д хуваасан үлдэгдлийг олцгооё. a тоо маш олон оронтой байж болох тул бид string ашиглан уншина. Энэ тооны оронгийн тоо нь s = a.size() гэвэл a = a[s-1]*(10^0)+a[s-2]*(10^1)+a[s-3]*(10^2)+...+a[0]*(10^s-1) байх ба a%p = (a[s-1]*(10^0)%p+a[s-2]*(10^1)%p+a[s-3]*(10^2)%p+...+a[0]*(10^s-1)%p)%p байна. Одоо b гэдэг тоог харцгаая. b = k*(p-1)+l байдаг гэе(l<p-1). Тэгвэл a^b%p = (a^(k*(p-1)+l)%p = a^(k*(p-1))*a^l%p эндээс нөгөөх теорем ...
Алгоритмын хичээл