【CCPC】CCPC 2023 Shenzhen Site I
Indeterminate Equation
#质因子分解 #数学 #二分 #分治
题目描述
Given positive integers n, k, find the number of positive integer solutions to the indeterminate equation a k − b k = n a^k − b^k = n ak−bk=n
输入格式
The first line of input is an integer T
(
1
≤
T
≤
20
)
(1 ≤ T ≤ 20)
(1≤T≤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
≤
n
≤
1
0
18
1 ≤ n ≤ 10^{18}
1≤n≤1018,
3
≤
k
≤
64
3 ≤ k ≤ 64
3≤k≤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^k - b^k
ak−bk,我能够提出一个
(
a
−
b
)
(a-b)
(a−b),例如当
k
=
3
k=3
k=3时,我们可以得到
a
3
−
b
3
=
(
a
−
b
)
(
a
2
+
a
b
+
b
2
)
a^3-b^3 = (a-b)(a^2+ab+b^2)
a3−b3=(a−b)(a2+ab+b2)
由于 n ≤ 1 e 18 n\leq 1e18 n≤1e18,所以我们可以通过大数质因子 p o l l a r d − r h o pollard-rho pollard−rho分解出所有 n n n的质因子,然后跑 d f s dfs dfs搜索出所有的因子,因为在 1 e 18 1e18 1e18以内,因子个数不超过 1 e 5 1e5 1e5个。
那么我们就可以枚举 n n n的因子作为 a − b a-b a−b的值,二分出满足条件的 b b b即可。
注意 a k − b k a^k -b^k ak−bk极有可能爆 _ _ i n t 128 \_\_int128 __int128,因此我们需要提前找出一个 a k − b k ≤ n a^k - b^k \leq n ak−bk≤n的上界。
由于当 k = 3 k=3 k=3时,上界可以到达接近 5 e 8 5e8 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_back
if (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;
上一篇:
HALCON 数据结构 - 数组