免费搭建网页游戏平台_律师关键词推广_网络推广怎么样_推广之家app下载

Indeterminate Equation

#质因子分解 #数学 #二分 #分治

题目描述

Given positive integers n, k, find the number of positive integer solutions to the indeterminate equation $a^k-b^k=n$

输入格式

The first line of input is an integer T $(1\le T\le 20)$ indicating the number of queries. The following T lines,
each contain two integers n, k indicating a single query. It is guaranteed that$1\le n\le 10^{18}$, $3\le k\le 64$.

输出格式

For each query, output a single line contains a single integer, indicating the answer

样例 #1

样例输入 #1

3
7 3
15 4
31 5

样例输出 #1

1
1
1

解法

解题思路

首先对于$a^k-b^k$，我能够提出一个$(a-b)$，例如当$k=3$时，我们可以得到
$$a^3-b^3=(a-b)(a^2+ab+b^2)$$

由于$n\le 1e18$，所以我们可以通过大数质因子$pollard-rho$分解出所有$n$的质因子，然后跑$dfs$搜索出所有的因子，因为在$1e18$以内，因子个数不超过$1e5$个。

那么我们就可以枚举$n$的因子作为$a-b$的值，二分出满足条件的$b$即可。

注意$a^k-b^k$极有可能爆$\_\_int128$，因此我们需要提前找出一个$a^k-b^k\le n$的上界。

由于当$k=3$时，上界可以到达接近$5e8$，我们特判一下这个情况即可。

代码

using pii = std::pair<int, int>;const int N = 2e5 + 10;int mul(int a, int b, int m)
{int r = a * b - m * (int)(1.L / m * a * b);return r - m * (r >= m) + m * (r < 0);
}
int mypow(int a, int b, int m)
{int res = 1 % m;for (; b; b >>= 1, a = mul(a, a, m)){if (b & 1){res = mul(res, a, m);}}return res;
}
int B[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
int ctz(unsigned int n) {if (n == 0) return 32; // 处理边界情况int count = 0;while ((n & 1) == 0) {n >>= 1;count++;}return count;
}bool MR(int n)
{if (n <= 1)return 0;for (int p : B){if (n == p)return 1;if (n % p == 0)return 0;}int m = (n - 1) >> ctz(n - 1);for (int p : B){int t = m, a = mypow(p, m, n);while (t != n - 1 && a != 1 && a != n - 1){a = mul(a, a, n);t *= 2;}if (a != n - 1 && t % 2 == 0)return 0;}return 1;
}int PR(int n)
{for (int p : B){if (n % p == 0)return p;}auto f = [&](int x) -> int{ x = mul(x, x, n) + 1; return x >= n ? x - n : x; };int x = 0, y = 0, tot = 0, p = 1, q, g;for (int i = 0; (i & 255) || (g = std::gcd(p, n)) == 1; i++, x = f(x), y = f(f(y))){if (x == y){x = tot++;y = f(x);}q = mul(p, std::abs(x - y), n);if (q)p = q;}return g;
}std::vector<int> fac(int n) {
#define pb emplace_backif (n == 1)return {};if (MR(n))return { n };int d = PR(n);auto v1 = fac(d), v2 = fac(n / d);auto i1 = v1.begin(), i2 = v2.begin();std::vector<int> ans;while (i1 != v1.end() || i2 != v2.end()){if (i1 == v1.end()){ans.pb(*i2++);}else if (i2 == v2.end()){ans.pb(*i1++);}else{if (*i1 < *i2){ans.pb(*i1++);}else{ans.pb(*i2++);}}}return ans;
}__int128_t quick(__int128_t x, int n)
{__int128_t res = 1;while (n){if (n & 1)res = (res * x);x = x * x;n >>= 1;}return res;
}std::ostream& operator<<(std::ostream& os, __int128_t n) {std::string s;while (n) {s = s + std::to_string((int)n % 10);n /= 10;}std::reverse(s.begin(), s.end());return os << s;
}std::vector<int> getfac(int n) {std::vector<int> pos = fac(n);std::map<int, int> cnt;for (auto i : pos) cnt[i]++;std::vector<pii> tmp;for (auto& [x, y] : cnt) tmp.push_back({ x, y });int len = tmp.size();std::set<int> st;auto dfs = [&](auto&& self, int mul, int dep) ->void {if (n % mul == 0)st.insert(mul);if (dep == len)return;int p = 1;for (int i = 0; i <= tmp[dep].second; i++) {if (i != 0)p *= tmp[dep].first;self(self, mul * p, dep + 1);}};dfs(dfs, 1, 0);std::vector<int>res;for (auto& x : st) res.emplace_back(x);return  res;
}void solve()
{int n, k;std::cin >> n >> k;int limit = 0,res = 0;if (k == 3) {limit = 5e8;}for (int i = 1; i <= 1e6; i++) {if (quick(i, k) - quick(i - 1, k) > n) {limit = i;break;}}auto factor = getfac(n);for (auto x : factor) {int l = 1, r = limit ,ans = 0;while (l <= r) {int mid = l + r >> 1;__int128_t a = mid + x, b = mid;int ok = 0;a = quick(a, k), b = quick(b, k);if (a - b == n) {ans = mid;break;}else if (a - b > n) r = mid - 1;else l = mid + 1;}res += ans;}std::cout << res << "\n";}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;std::cin >> t;while (t--) {solve();}
};