Թվի արագ աստիճան բարձրացում

cmath գրադարանիpow ֆունկցիան շատ օգտակար է, բայց այն բավական դանդաղ է ու որոշ հաշվարկների համար հնարավոր չէ այն օգտագործել։

Եթե մենք պետք է հաշվենք արտահայտության արժեքը և գիտենք, որ օրինակ a = 3իսկ b = 64, ապա շատ ավելի արագ ձև կա այս արտահայտությունը հաշվելու համեմատ 64 անգամ արդյունքը a-ով բազմապատկելը։

Ունենալով, որ b-ն 2-ի աստիճան է, խնդիրը շատ է հեշտանում։

res = a;            // res = 3    (3^1)
res = res * res;    // res = 9    (3^2)
res = res * res;    // res = 81   (3^4)
res = res * res;    // res = 6561 (3^8)
res = res * res;    // res = 43046721 (3^16)
res = res * res;    // res = 1853020188851841 (3^32)
res = res * res;    // res = 3433683820292512484657849089281 (3^64)

Այսպիսով մենք կատարեցինք միայն 6 բազմապատկման գործողություն, 64-ի փոխարեն և կարողացանք հաշվել արտահայտության արժեքը։ Բնականաբար C++ի int կամ long long տիպերում այս թիվը չի տեղավորվի, այնպես որ եթե անգամ այսպիսի արժեք պետք գա, այն ամենայն հավանականությամբ պետք կգա ինչ-որ թվի վրա բաժանելուց ստացվող մնացորդ հաշվելուց հետո (որպեսզի C++ի ստանդարտ տիպերի մեջ տեղավորվի)։

Անհրաժեշտ է գրել ֆունկցիա long long binpow(int a, int b, int m) որը արագ կհաշվի արտահայտության արժեքը։

Մուտքում տրված է երեք ամբողջ թիվ՝ a, b և m-ը (1 ≤ a, m ≤ , 0 ≤ b ≤ )։ Գրեք binpow անունով ֆունկցիա, որը կհաշվի և ելքի միակ տողում տպեք այդ արտահայտության արժեքը։ Երաշխավորվում է որ b-ն երկուսի աստիճան է։