Алгоритм програмчлал.

Шинэ жил боллоо. Гэсэн ч ахиад л зэрэг. Өнөөх л a^b%mod-оо бодоцгооё. Бид хувиргалт хийгээд a, b < mod болгож чадна. Харин mod <= 10^13 гэвэл a^b бодох явцад үржвэр нь хамгийн ихдээ ойролцоогоор 10^26 болох юм. Гэтэл long long төрөлд үүнийг хийж чадах билүү? Тэгхээр өмнөх бодолтууд зөв биш гэдгийг анзаарсан байх. Үүнийг хэрхэн шийдэх вэ? Асуудал нь үржих үйлдэл нь том тооны хувьд асуудалтай байгаа тул үүнийг зөв олох хэрэгтэй. x*(y/2)%mod -г мэдэж байхад бид x*y олж чадна. Өмнө нь ашиглаж байсан санаа буюу a^b олсон бодлоготой адил болж байна.

Юм хийхгүй байсан ч хугацаа өнгөрдөг юм байна. Дахиад 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 эндээс нөгөөх  теорем ...

Үүгээр чадах бодлого болон алгоритмын анализ эхэлж байгаа ба өмнөх оруулсан зүйлсийг мэдэж байхад энэ бүгдийг ойлгоход асуудал үүсэхгүй байх. A тооны B зэргийг 10^9+7 гэх анхны тоонд модулдаж гарсан хариуг ол. A, B<=10^13. Бид энгийн давталт ашиглан үүнийг олж чадах юм. Гэвч үүнийг олохын тулд B үйлдэл хийх ба энэ нь 10^13 тул маш удаан ажиллана. Үүнийг хэрхэн хурдан хугацаанд шийдэх вэ? B тоо нь хоёртын бичиглэлдээ B=x[0]*(2^0)+x[1]*(2^1)+...+x[k]*(2^k) гэж задардаг байг. Тэгвэл k<=log(10^13) байх юм. Тэгвэл бид A^1, A^2, A^3, ... , A^k гэх мэт k ширхэг тоонуудыг k үйлдлээр байгуулна. Одоо энэ хоёрыг угсарвал A^B=(A^(x[0]*(2^0)))*(A^(x[1]*(2^1)))*...*(A^(x[k]*(2^k))) болох юм. Ингэснээр бид k үйлдлээр A тооны B зэргийг олж чадаж байна. Хэрвээ B тоо нь тэгш бол A^B=(A^(B/2))*(A^(B/2)) харин сондгой үед A^B=(A^(B/2))*(A^(B/2))*A гэдэг нь тодорхой юм. Эндээс бид A тооны B зэргийг мэдэхийг хүсвэл A тооны B/2 зэргийг мэдэж байхад олж чадна гэдэг нь харагдаж байна. Тэгвэл A тооны...