【P8302 题解】-526互联

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\)。

也就是求出循环的开始位置。

\(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\) 本身已经在循环内，不用操作。

代码：

#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;
}