题目大意

定义一次「操作」为将一个正整数 除以或乘以一个质数。
定义函数 ( d(a, b) ) 表示将 ( a ) 变成 ( b ) 所需的最小操作次数。
给定 ( n ) 个正整数 ( a_1, a_2, \dots, a_n )，对每个 ( a_i )，求一个 ( j \neq i ) 使得 ( d(a_i, a_j) ) 最小，若多个则取最小的 ( j )。

思路分析

1. 理解 ( d(a, b) ) 的本质

设 ( a = p_1^{k_1} p_2^{k_2} \dots )，( b = p_1^{m_1} p_2^{m_2} \dots )，则
[ d(a, b) = \sum |k_i - m_i| ] 因为每次乘以或除以一个质数，相当于某个质因子的指数变化 1。

换句话说，( d(a, b) ) 就是 质因子指数差的绝对值之和。

2. 转化为更易处理的形式

设 ( f(x) ) 表示 ( x ) 的质因子指数之和（即质因子分解后指数相加）。
那么： [ d(a, b) = f\left( \frac{a}{\gcd(a, b)} \right) + f\left( \frac{b}{\gcd(a, b)} \right) ] 因为：

• 对于公共质因子，指数相同，差为 0。
• 对于不同的部分，就是各自去掉最大公约数后的质因子指数之和。

3. 问题转化

对于每个 ( a_i )，我们要找 ( j \neq i ) 使得： [ f\left( \frac{a_i}{\gcd(a_i, a_j)} \right) + f\left( \frac{a_j}{\gcd(a_i, a_j)} \right) ] 最小。

设 ( g = \gcd(a_i, a_j) )，那么： [ d(a_i, a_j) = f\left( \frac{a_i}{g} \right) + f\left( \frac{a_j}{g} \right) ] 其中 ( g ) 是 ( a_i ) 和 ( a_j ) 的公约数。

4. 核心优化

我们可以枚举 ( a_i ) 的所有约数 ( d )，然后考虑所有能被 ( d ) 整除的 ( a_j )，那么 ( \gcd(a_i, a_j) ) 至少是 ( d )。

对于固定的 ( d )，我们想最小化： [ f\left( \frac{a_i}{d} \right) + f\left( \frac{a_j}{d} \right) ] 其中 ( d \mid a_j )。

对于每个 ( d )，我们只需要保留 最小的两个 ( f\left( \frac{a_j}{d} \right) ) 对应的 ( j )（因为可能有一个是 ( a_i ) 自己，需要排除）。

5. 算法步骤

1. 预处理 ( f(x) )（质因子指数和）：

   • 用类似筛法的方式计算，( f[i \cdot p] = f[i] + 1 )（( p ) 是质数）。

2. 对每个 ( a_i ) 预处理它的所有约数（因为 ( a_i \leq 10^6 )，约数个数不会太多）。

3. 对每个 ( d )，维护一个大小为 2 的堆（或排序保留最小的两个），记录最小的 ( f(a_j / d) ) 和对应的 ( j )。

4. 对每个 ( a_i )：

   • 枚举它的约数 ( d )，
   • 在 ( d ) 对应的最小两个值中，排除 ( i ) 自己，计算 ( f(a_i / d) + f(a_j / d) )，
   • 取最小的 ( j )。

6. 时间复杂度

• 预处理 ( f(x) )：( O(M \log \log M) )，( M = 10^6 )。
• 预处理每个数的约数：( O(M \log M) )。
• 每个数约数个数平均很少，总体可行。

代码实现

#include "bits/stdc++.h"
using namespace std;

const int MAX_A = 1e6 + 5;
const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // 预处理质因子指数和 f(x)
    vector<int> f(MAX_A, 0);
    for (int i = 2; i < MAX_A; i++) {
        if (f[i] == 0) { // i 是质数
            for (int j = i; j < MAX_A; j += i) {
                int x = j, cnt = 0;
                while (x % i == 0) {
                    x /= i;
                    cnt++;
                }
                f[j] += cnt;
            }
        }
    }

    vector<int> a(n);
    // 预处理每个 a[i] 的约数
    vector<vector<int>> divisors(MAX_A);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (divisors[a[i]].empty()) {
            for (int d = 1; d * d <= a[i]; d++) {
                if (a[i] % d == 0) {
                    divisors[a[i]].push_back(d);
                    if (d != a[i] / d) {
                        divisors[a[i]].push_back(a[i] / d);
                    }
                }
            }
        }
    }

    // 对每个 d，保留 f(a[j]/d) 最小的两个 j
    vector<pair<int, int>> best[MAX_A]; // (f_value, index)
    for (int i = 0; i < n; i++) {
        int x = a[i];
        for (int d : divisors[x]) {
            int val = f[x / d];
            best[d].emplace_back(val, i);
            // 保持 best[d] 大小 <= 2
            if (best[d].size() > 2) {
                sort(best[d].begin(), best[d].end());
                best[d].pop_back();
            }
        }
    }

    // 对每个 a[i] 找答案
    for (int i = 0; i < n; i++) {
        int x = a[i];
        pair<int, int> ans = {INF, INF}; // (distance, index)
        for (int d : divisors[x]) {
            if (best[d].size() < 2) continue;
            // 找到不是 i 的那个
            int idx = 0;
            if (best[d][idx].second == i) idx++;
            int dist = f[x / d] + best[d][idx].first;
            ans = min(ans, {dist, best[d][idx].second});
        }
        cout << ans.second + 1 << '\n';
    }

    return 0;
}

总结

这道题的关键在于：

1. 将 ( d(a, b) ) 转化为质因子指数差的绝对值和。
2. 利用最大公约数将问题转化为枚举公约数 ( d )。
3. 对每个 ( d ) 维护最小的两个 ( f(a_j / d) ) 来快速查询。

这样就能在 ( O(M \log M + n \cdot \text{约数个数的平均值}) ) 时间内解决。