Solution
设 \(g(x)\) 表示 \(x\) 的最小质因子。
则 \(f(x)=n+\dfrac{n}{g(x)}=\dfrac{g(x)+1}{g(x)}\times n\)。
分情况讨论：
-
\(g(x)=2\)，经过 \(1\) 次变换之后，\(f(x)\) 增加了一个因子 \(3\)，减少了一个因子 \(2\)。
-
\(g(x)>2\)，则满足 \(g(x)\nmid 2\)，否则与最小质因子矛盾，经过 \(1\) 次变化之后，\(f(x)\) 增加一个因子 \(2\)。
设 \(n=2^p\times x\) 且 \(2\nmid x\)，经过 \(p\) 次操作，\(n=3^p\times x\)，再经过 \(1\) 次操作，\(n=2^2\times 3^{p-1}\times x\)，再经过 \(2\) 次操作后，\(n=3^{p+1}\times x\)，我们发现，\(n=3^p\times x\) 后，每 \(3\) 次操作一循环。
如果 \(m\) 不在循环中，因为 \(2\) 的因子一定是单调递减的，所以一定不满足 \(f^{(m)}(n)\mid f^{(m+k)}(n)\)。
如果 \(m\) 在循环中，那么当且仅当 \(k=3q, q\in\mathbb{Z}\)，满足 \(f^{(m)}(n)\mid f^{(m+k)}(n)\)，手玩一下即可。
综上，\(3\mid k\) 是有解的充分必要条件。
考虑如何求出最小的自然数 \(m_0\)。
也就是求出循环的开始位置。
如果一个数 \(n=2^p\times x, 2\nmid x\) 在循环里，则满足 \(0\le p\le 2\)。
-
\(2\nmid n, 3\nmid n\)，先进行一次操作，将 \(n\to n+\dfrac{n}{minp_n}\)，其中 \(minp_n\) 表示 \(n\) 的最小质因子，再进行如下操作。
-
\(2\mid n\)，\(n=2^p\times x\)，其中 \(2\nmid x\)，需要进行 \(\max\{0,p-2\}\) 次操作将 \(p\) 变成 \(2^{\min\{2, p\}}\times x\)，此时 \(n\) 已经在循环内。
-
\(2\nmid n, 3\mid n\)，\(n\) 本身已经在循环内，不用操作。
\(minp\) 可以用线性筛法 \(\mathcal O(n)\) 求出。
时间复杂度为：\(\mathcal O(n+T\log n)\)。
代码：
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 30000010;
std::vector<int> minp, primes;
void sieve(int n) {
minp.assign(n + 1, 0);
primes.clear();
for (int i = 2; i <= n; i ++ ) {
if (minp[i] == 0) {
minp[i] = i;
primes.push_back(i);
}
for (auto p : primes) {
if (i * p > n) {
break;
}
minp[i * p] = p;
if (p == minp[i]) {
break;
}
}
}
}
void solve() {
int n, k;
std::cin >> n >> k;
if (k % 3) {
std::cout << -1 << "\n";
return;
}
if (n % 2 && n % 3 == 0) {
std::cout << 0 << "\n";
return;
}
int x = -2, y = 0;
if (n % 2 && n % 3) {
n = n / minp[n] * (minp[n] + 1);
y ++ ;
}
while (n % 2 == 0) {
x ++ ;
n /= 2;
}
std::cout << std::max(0, x) + y << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
sieve(N);
int t;
std::cin >> t;
while (t -- ) {
solve();
}
return 0;
}