题解：P9179 [COCI2022-2023#5] Logaritam
LZC_AK_CRZ
·
·
题解
Solution
一、思考过程
$\because a_i=a_{1*i}=a_1+a_i
\therefore a_1=0
即当修改下标 x=1 时，无解（输出 -1）。
修改下标为 $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)$。
三、代码
```cpp
#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;
}
```