1245 : 不定方程
Time Limit: 1 Sec Memory Limit: 512 Mb Submitted: 1237 Solved: 184Description
给定正整数 \(n,k\),求不定方程 \(a^k-b^k=n\) 的正整数解数量。
Input
输入第一行一个整数 \(T\)(\(1 \le T \le 20\)) 表示询问数量。之后 \(T\) 行,每一行两个整数 \(n,k\) 表示一次询问。保证 \(1 \le n \le 10^{18}\),\(3 \le k \le 64\)。
Output
对于每一组询问,输出一行一个非负整数表示答案。
Sample
3 7 3 15 4 31 5
1 1 1
Hint
【样例解释 #0】
三个不定方程的唯一解都是 \((2,1)\)。
Author
THU