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

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

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

快速冪介紹：

       我們1直說快速冪快，那他究竟是在哪里快呢? 如果我們求解 2^k?？梢詫⑵浔硎緸?/p>

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

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

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

      就有

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

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

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

快速冪的模板：

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

遞歸版的：

下面附上本題的代碼：

（如有毛病，歡迎指正，轉載請注明出處）

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈