文章目录

1. 1. Super Pow

Super Pow

---

这道题目我一开始是用迭代b次，就是把vector b求和计算，然后result = (result*b)%1337，但是后来发现b太大了，根本不能求和，所以我们得换个思路来。

这里我们得知道两个数学知识：

1. (a*b)%n = ((a%n)*(b%n)) % n
2. (a^c)%n = (a%n)^c % n

第一条可以帮我们处理当a*b溢出的情况

第二条用来处理位数，比如

a^1234567 % n = (a^1234560 * a^7)%n = ( (a^1234560 %n) * (a^7%n) )% n

其中a^1234560%n套用第二条就变成了(a^123456%n)^10 % n

那么回到题目由于b是一个表示一个数的各数位上数的vector

从数字的最高位（0）到数字的最低位（v.size()）遍历vector

访问到第i位的数位时，result表示a^v[0…i-1]%n的结果，那么a^v[0…i] = (a^(v[0…i-1]*10)*a^v[i])%n

= (result^10%n)*(a^v[i]%n) %n

这里还要介绍一个montgory蒙特格里算法，我之前的做法求a^b%k的复杂度是O(b)的，太大了，实际上可以是O(logb)的

我们将b用二进制形式表示，比如13是1101，其实就是8+4+0+1 = 1*2^3 + 1*2^2 + 0*2^2 + 1^2^0

那么我们对b每次与1按位1取出二进制表示形式的最后一位，如果是1的话，result = (result*base)%k;是0的话不做处理直到b变成0。在循环中需要每次对b左移1位才行，同时在最后的时候更新base=(base*base)%k