P9179 [COCI 2022/2023 #5] Logaritam

定义对数序列为一个长为 $n$ 的对数序列 $(a_1,a_2,\ldots,a_n)$，满足对于所有正整数 $x,y$ 且 $xy\le n$，有 $a_{xy}=a_x+a_y$。一个长为 $6$ 的对数序列例子为 $0,1,\pi,2,0.7,1+\pi$。 有 $q$ 个长度为 $n$ 的对数序列，但是现在每个序列都恰好有一个元素被改掉了。给你序列个数 $q$，序列长度 $n$ 和每个序列被改动的元素位置 $x_i$，对于每个序列，输出在不改动已经更改的元素的情况下，至少要修改序列中多少个位置的元素才能使这个序列仍然是对数序列。 注：可以证明对于任意的初始对数序列，改动同一位置后，在不改动这个位置的情况下将序列变为对数序列的最小改动数都是相等的。

第一行两个正整数 $n,q\ (1\le n\le 10^8,1\le q\le 10^4)$，分别表示序列长度和序列个数。 接下来 $q$ 行，第 $i$ 行一个正整数 $x_i\ (1\le x_i\le n)$，表示第 $i$ 个序列中修改的元素下标。

如果第 $i$ 个序列无法在不改动已经更改的元素的情况下，将原序列变为对数序列，则输出 `-1`，否则输出最少更改元素个数。

样例 $1$ 解释： 假设初始序列是 $0,1,\pi,2,0.7,1+\pi$，修改第四个元素为 8，那就可以把第二个元素改为 $4$，把第六个元素改为 $4+\pi$，这样序列变成 $0,4,\pi,8,0.7,4+\pi$，又变成了对数序列。 |子任务编号| 附加限制| 分值| |:-:|:-:|:-:| |$0$| 是样例 |$0$| |$1$| $n\le 20,q\le 20$ |$17$| |$2$| $q\le 8$ |$24$| |$3$| $n\le 10^4$ |$26$| |$4$| 无附加限制 |$33$|