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