372. Super Pow

Your task is to calculate?a^b?mod 1337 where?a?is a positive integer and?b?is an extremely large positive integer given in the form of an array.

Example1:

a = 2 b = [3]Result: 8

Example2:

a = 2 b = [1,0]Result: 1024

?

計算a^b%1337，其中a、b均為正整數，且b非常大，用一個數組表示每一位數字。

分析：

　　直接a自乘b次，再對1337求余，雖然理論上可行，但是存在兩個很大的問題：

溢出；

執行效率太低。

所以必須進行優化。

　　對于1，我們知道a^b%n=(a%n)^b%n，因此，可先將a對1337求余，以將a調整到1337以內，若a是個很大的數，這樣做可顯著的降低計算的數量級。

　　對于2，因為b是一個非常大的數，我們不能一次一次乘。可通過二分法來優化。

　　此外，由于b以數組的形式表示，我們知道，a^k=（a^k₀*10）*（a^k₁），其中k為一個兩位數，k₀為k的10位數，k₁為k的個位數。因此，我們可從b的最高位開始計算（第0個元素），將a^b[0]結果存儲在rst中，接著取出b[1]，計算a^b[1]，將rst更新為（rst¹⁰）*（a^b[1]），然后取出b[2]，rst更新為（rst¹⁰）*（a^b[2]），…，如此循環，直至b中最后一個元素。注意在每次更新rst時，可先對1337求余，以降低數量級。

代碼如下：

int pow(int x, int n) {if (n == 0)return 1;if (n == 1)return x % 1337;if (x == 1)return 1;int rst = 1, tmp = x;while (n > 0){if (n % 2)rst = rst*tmp % 1337;tmp = tmp*tmp % 1337;n /= 2;}return rst % 1337; }int superPow(int a, vector<int>& b) {int rst = 1;a %= 1337;for (int i = 0; i < (int)b.size(); i++)rst = pow(rst, 10)*pow(a, b[i]) % 1337;return rst; }

　　

posted on 2018-03-23 11:05 bigpotato 閱讀(...) 評論(...) 編輯 收藏

轉載于:https://www.cnblogs.com/big-potato/p/8628897.html

總結

以上是生活随笔為你收集整理的372. Super Pow的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。