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

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int v[N],p[N],pr;
void init()
{
	for(int i=2;i<=N-10;i++)
	{
		if(!v[i])p[++pr]=i;
		for(int j=1;(j<=pr)&&(i*p[j]<=N-10);j++)
		{
			v[i*p[j]]=1;
			if(i%p[j]==0)break;
		}
	}
}
signed main()
{
	init();
	int n,q;cin>>n>>q;
	while(q--)
	{
		int x,ans=0;cin>>x;
		if(x==1){cout<<-1<<'\n';continue;}
		for(int i=1;i<=pr;i++)
			while(x%p[i]==0)ans=max(ans,p[i]),x/=p[i];
		ans=max(ans,x);
		cout<<(n/ans-1)<<'\n';
	}
	return 0;
}