问题
设2 ≤ a ≤ 5 且 2 ≤ b ≤ 5，下面为\(a^b\)的所有值：
\(2^2=4, 2^3=8, 2^4=16, 2^5=32\)
\(3^2=9, 3^3=27, 3^4=81, 3^5=243\)
\(4^2=16, 4^3=64, 4^4=256, 4^5=1024\)
\(5^2=25, 5^3=125, 5^4=625, 5^5=3125\)
将它们按数值顺序从小到大排列，剔除重复项，我们会得到如下15个各不相同的指数值：
\(4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125\)请问，设2 ≤ a ≤ 100 且 2 ≤ b ≤ 100，有多少个各不相同的指数值？
* 传送门
分析
显然本题用暴力解题也不会十分耗时，一万次循环以内就可以找到答案。问题是有些值直接用内置数值类型进行指数运算会出现溢出问题，所以就需要用到BigInteger。
当然，通过笔算也能解题。
首先，所有组合的指数值总共有99*99=9801个。
哪些指数值会重复呢？底数本身是n次方数的情况下会有重复。
在题目例子中\(4^2\)和\(2^4\)重复了，因为\(4^2 = (2^2)^2 = 2^{2\cdot2} = 2^4\)。可见，作为底数的4本身就是\(2^n\)形态，所以会造成重复。当底数为a=4时，\(2 \leq b \leq 50\)都会和当底数为a=2、\(4 \leq b \leq 100\)且b为偶数的情况重复。
即当底数a=4时，有49个重复项。9801 – 49 = 9752。
如此类推，当底数\(a=8=2^3\)，\(2 \leq b \leq 33\)都会和当底数为a=2、\(6 \leq b \leq 99\)且b为3的倍数的情况重复，这便有32项重复。而\(34 \leq b \leq 66\)且b为偶数时，又会与底数为4、\(51 \leq b \leq 99\)且b为3的倍数的情况重复，这便有17项重复。
即当底数a=8时，有49个重复项。9752 – 49 = 9703。
同样，当底数\(a=9=3^2\)，\(2 \leq b \leq 50\)都会和当底数为a=3、\(4 \leq b \leq 100\)且b为偶数的情况重复。
即当底数a=9时，有49个重复项。9703 – 49 = 9654。
当底数\(a=16=4^2\)，\(2 \leq b \leq 50\)都会和当底数为a=4、\(4 \leq b \leq 100\)且b为偶数的情况重复，这便有49项重复。而\(51 \leq b \leq 75\)且b为3的倍数时，又会与底数为8、\(68 \leq b \leq 100\)且b为4的倍数的情况重复，这便有9项重复。
即当底数a=16时，有58个重复项。9654 – 58 = 9596。
同样，当底数\(a=25=5^2\)，\(2 \leq b \leq 50\)都会和当底数为a=5、\(4 \leq b \leq 100\)且b为偶数的情况重复。
即当底数a=25时，有49个重复项。9596 – 49 = 9547。
当底数\(a=27=3^3\)，\(2 \leq b \leq 33\)都会和当底数为a=3、\(6 \leq b \leq 99\)且b为3的倍数的情况重复，这便有32项重复。而\(34 \leq b \leq 66\)且b为偶数时，又会与底数为9、\(51 \leq b \leq 99\)且b为3的倍数的情况重复，这便有17项重复。
即当底数a=27时，有49个重复项。9547 – 49 = 9498。
当底数\(a=32=2^5\)，\(2 \leq b \leq 20\)都会和当底数为a=2、\(10 \leq b \leq 100\)且b为5的倍数的情况重复，这便有19项重复。而\(22 \leq b \leq 40\)且b为偶数时，又会与底数为4、\(55 \leq b \leq 100\)且b为5的倍数的情况重复，这便有10项重复。而\(44 \leq b \leq 80\)且b为4的倍数时，又会与底数为16、\(55 \leq b \leq 100\)且b为5的倍数的情况重复，这便有10项重复。而\(21 \leq b \leq 57\)且b为3的倍数时，又会与底数为8、\(35 \leq b \leq 95\)且b为5的倍数的情况重复，这便有13项重复，其中\(32^{24}, 32^{30}, 32^{36}, 32^{48}\)这4项在前面早已计算在内。所以实际的重复项为19+10+10+13-4=48。
即当底数a=32时，有48个重复项。9498 – 48 = 9450。
当底数\(a=36=6^2\)，\(2 \leq b \leq 50\)都会和当底数为a=6、\(4 \leq b \leq 100\)且b为偶数的情况重复。
即当底数a=36时，有49个重复项。9450 – 49 = 9401。
当底数\(a=49=7^2\)，\(2 \leq b \leq 50\)都会和当底数为a=7、\(4 \leq b \leq 100\)且b为偶数的情况重复。
即当底数a=49时，有49个重复项。9401 – 49 = 9352。
当底数\(a=64=2^6\)，\(2 \leq b \leq 50\)都会和当底数为a=6、\(4 \leq b \leq 100\)且b为偶数的情况重复，这便有49项重复。而\(55 \leq b \leq 80\)且b为5的倍数时，又会与底数为32、\(66 \leq b \leq 96\)且b为6的倍数的情况重复，这便有6项重复。而\(52 \leq b \leq 66\)且b为偶数时，又会与底数为16、\(78 \leq b \leq 99\)且b为3的倍数的情况重复，这便有8项重复，而这8项中又有一项\(64^{60}\)与前面重复，所以实际的重复项为49+6+8-1=62。
即当底数a=64时，有62个重复项。9352 – 62 = 9290。
当底数\(a=81=9^2\)，\(2 \leq b \leq 50\)都会和当底数为a=9、\(4 \leq b \leq 100\)且b为偶数的情况重复，这便有49项重复。而\(51 \leq b \leq 75\)且b为3的倍数时，又会与底数为27、\(68 \leq b \leq 100\)且b为4的倍数的情况重复，这便有9项重复。
即当底数a=81时，有58个重复项。9290 – 58 = 9232。
当底数\(a=100=10^2\)，\(2 \leq b \leq 50\)都会和当底数为a=10、\(4 \leq b \leq 100\)且b为偶数的情况重复。
即当底数a=100时，有49个重复项。9232 – 49 = 9183。
规律便是，平方数、立方数为底重复49次，4次方数为底比平方数为底再重复多9次、即58次，5次方数为底和6次方数为底的数要仔细观察。
答案
// answer: brute force
const start = Date.now()
const powers = {}
let result = 0
for (let a = 2; a <= 100; ++a) {
const _a = bigInt(a)
for (let b = 2; b <= 100; ++b) {
const p = _a.pow(b).toString()
if (!(p in powers)) {
powers[p] = true
result++
}
}
}
alert(result + ', ' + (Date.now() - start) + 'ms')
