Үүгээр чадах бодлого болон алгоритмын анализ эхэлж байгаа ба өмнөх оруулсан зүйлсийг мэдэж байхад энэ бүгдийг ойлгоход асуудал үүсэхгүй байх. 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 тооны B/2 зэргийг олохыг хүсвэл A тооны B/4 зэргийг олоход л хангалттай юм. Энэ мэтчилэн B тоо нь 1 гэсэн тоотой тэнцүү болоход A^B = A ба үүнийг бид шууд мэдэж чадна. Одоо бид үүнийг рекурсив ашиглан шийдэж чадах юм. Мөн хугацааны үнэлгээ нь log(B) болох юм.
Доорх код нь энэ хаяг дээр байгаа.
- // A тооны B зэргийг 10^9+7 гэх анхны тоонд модулдаж гарсан хариуг ол. A, B <= 10^13
- #include <iostream>
- using namespace std;
- long long mod = 1e9+7;
- // 1e9 гэдэг нь 10^9 үржих нь 1 гэсэн утгатай.
- long long bodolt1( long long A, long long B ) {
- long long ret = 1, now = A;
- // ret гэдэг хувьсагч нь хариу болох хувьсагч ба анхны утга нь A^0 буюу 1
- // now гэдэг хувьсагч нь A тооны 2^k зэргийн авах ба анхны утга нь
- // A^(2^0) буюу A байх юм.
- while( B > 0 ) { // Хэрвээ B нь тэгээс их бол хоёртын бичиглэлд нь
- // хөрвүүлж дуусаагүй байна гэсэн үг.
- if( B%2 == 1 ) { // Одоо байгаа B тоо нь 2-т хуваахад 1 үлддэг бол одоо
- // явж байгаа байрлалдах бит нь 1 байх тул үржвэрт орно.
- // эсрэг тохиолдолд 0 болох тул өнжиж болно.
- // одоо явж байгаа бит нь 1 тул A тооны одоо явж байгаа тоон зэргээр
- // үржигдэх ёстой гэсэн үг.
- ret = (ret*now)%mod;
- }
- // одоо энэ зэрэг нэгээр ахих буюу квадрат зэрэгт дэвшинэ гэсэн үг юм.
- now = (now*now)%mod;
- B /= 2; // B тоог 2т хувааж битийн байрлал ахина.
- }
- return ret; // хариуг буцааж байна.
- }
- long long bodolt2( long long A, long long B ) {
- if( B == 0 ) return 1LL; // Хэрвээ B тоо нь 0 бол 1-ыг буцаана. Тооны 0 зэрэг 1
- if( B == 1 ) return A; // Хэрвээ B тоо нь 1 бол A^1 буюу A тоо өөрөө юм.
- long long ret = bodolt2( A, B/2 );
- // ret хувьсагчийн одоо авж байгаа утга нь A тооны B/2 зэргийг олсон утга юм.
- ret = (ret*ret)%mod;
- // тиймээс үүнийг квадрат зэрэгт дэвшүүлнэ.
- if( B%2 == 1 ) {
- // хэрвээ сондгой бол A тоогоор үржихдэх ёстой.
- ret = (ret*A)%mod;
- }
- return ret; // A^B буцаах
- }
- int main() {
- long long A, B;
- cin >> A >> B;
- cout << "Bodolt1-> " << bodolt1( A%mod, B ) << endl;
- cout << "Bodolt2-> " << bodolt2( A%mod, B ) << endl;
- return 0;
- }
Comments
Post a Comment