hdu2035 人見人愛A^B（快速冪取模）

題目鏈接：hdu 2035 人見人愛A^B

      很早的時(shí)候做的1道題了，今天想一想把他翻了出來，寫篇文章來為不知道快速冪的同學(xué)做1個(gè)科普（請?jiān)试S我吹1下牛逼）。快速冪可以高效的計(jì)算冪運(yùn)算。如果我們使用循環(huán)來計(jì)算的話，那末時(shí)間復(fù)雜度就是 O(n) ，使用快速冪的話就只用 O(log n)。不要小視這么1點(diǎn)點(diǎn)，如果1個(gè)問題需要屢次 的 冪運(yùn)算的話，可能就會(huì)由于這1點(diǎn)小小的變化而超時(shí)。

快速冪介紹：

       我們1直說快速冪快，那他究竟是在哪里快呢? 如果我們求解 2^k。可以將其表示為

             x^n =( (x2)2....)

      只要做k次平方運(yùn)算就能夠了，由此我們可以想到，先將n表示為2的冪方次之和

             n = 2^k1 + 2^k2 + 2^k3.......

      就有

           x^n = x^(2^k1) x^(2^k2) x^(2^k3).......

     So.快速冪就是這么快。不太明白的可以用筆和紙手動(dòng)的摹擬1下。 

例如： x^22 = x^16?x^4?x^2

快速冪的模板：

沒看位運(yùn)算的童鞋，好好回去看看，好多地方都是用這東西

遞歸版的：

下面附上本題的代碼：

（如有毛病，歡迎指正，轉(zhuǎn)載請注明出處）

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)