自动搬运

查看原文

来自洛谷，原作者为

	LZC_AK_CRZ My heart will go on.

搬运于2025-08-24 22:46:05，当前版本为作者最后更新于2024-11-08 21:04:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

一、思考过程

$a)$ 无解情况：
$\because a_i=a_{1*i}=a_1+a_i$
$\therefore a_1=0$
即当修改下标 $x=1$ 时，无解（输出 $-1$）。

$b)$ 有解情况：
修改下标为 $x$ 的元素时，以 $x$ 的因数为下标的元素中必然会有至少一个被修改。设其中一个的下标为 $x_1$，同理则以 $x_1$ 的因数为下标的元素中必然会有至少一个被修改。显然这是一个递归过程，而终止条件则是得到的某一个因数 $x_k$ 为质数。那么贪心策略告诉我们，当 $x_1$ 为质数，即 $x_1$ 为 $x$ 的质因数时，需要的修改次数是最少的。
但是，当以 $x_1$ 为下标的元素被修改时，以 $x_1$ 的倍数为下标的元素也必然会被修改。所以总的修改个数为 $n/x_1-1$。又因为 $x_1$ 越大，修改个数越小，所以我们得到 $x_1$ 为 $x$ 的最大质因数。

二、复杂度分析

时间复杂度最大开销是寻找最大质因数的过程，我们可以用质因数分解解决，时间复杂度 $O(\sqrt n)$。又因为有 $q$ 次询问，所以总的时间复杂度 $O(q\sqrt n)$。瞄一眼数据范围，$1 \le q \le 10^4$, $1 \le n \le 10^8$, $q\sqrt n$ 最大 $10^8$，可以通过。
空间复杂度 $O(1)$。

三、代码

#include <iostream>
#define int long long //心里踏实
using namespace std;
int n, q, x;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> q;
    while (q--) {
        cin >> x;
        if (x == 1) {
            cout << -1 << '\n';
            continue;
        }
        int maxt = 0;
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) maxt = i;
            while (x % i == 0) x /= i;
        }
        if (x != 1) maxt = x;
        cout << (n - maxt) / maxt << '\n';
    }
    return 0;
}