Үүгээр чадах бодлого болон алгоритмын анализ эхэлж байгаа ба өмнөх оруулсан зүйлсийг мэдэж байхад энэ бүгдийг ойлгоход асуудал үүсэхгүй байх. 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 тооны
Алгоритмын хичээл