Թվի արագ աստիճան բարձրացում
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-ի փոխարեն և կարողացանք հաշվել
int կամ long long տիպերում այս թիվը չի տեղավորվի, այնպես որ եթե անգամ այսպիսի արժեք պետք գա, այն ամենայն հավանականությամբ պետք կգա ինչ-որ թվի վրա բաժանելուց ստացվող մնացորդ հաշվելուց հետո (որպեսզի C++ի ստանդարտ տիպերի մեջ տեղավորվի)։Անհրաժեշտ է գրել ֆունկցիա
long long binpow(int a, int b, int m) որը արագ կհաշվի Մուտքում տրված է երեք ամբողջ թիվ՝
a, b և m-ը (1 ≤ a, m ≤ , 0 ≤ b ≤ )։ Գրեք binpow անունով ֆունկցիա, որը կհաշվի b-ն երկուսի աստիճան է։Մուտք | Ելք |
3 8 17 | 16 |
Constraints
Time limit: 0.2 seconds
Memory limit: 512 MB
Output limit: 1 MB