P9179 [COCI 2022/2023 #5] Logaritam

A logarithmic sequence is defined as a sequence $(a_1,a_2,\ldots,a_n)$ of length $n$ such that for all positive integers $x,y$ with $xy\le n$, we have $a_{xy}=a_x+a_y$. An example of a logarithmic sequence of length $6$ is $0,1,\pi,2,0.7,1+\pi$. There are $q$ logarithmic sequences of length $n$, but now in each sequence exactly one element has been changed. You are given the number of sequences $q$, the sequence length $n$, and the position $x_i$ of the changed element in each sequence. For each sequence, output the minimum number of positions that must be modified so that the sequence is still a logarithmic sequence, under the condition that the already changed element must not be modified. Note: It can be proven that for any initial logarithmic sequence, after changing the same position, the minimum number of modifications needed to turn the sequence back into a logarithmic sequence (without modifying that position) is always the same.

The first line contains two positive integers $n,q\ (1\le n\le 10^8,1\le q\le 10^4)$, representing the sequence length and the number of sequences. The next $q$ lines each contain a positive integer $x_i\ (1\le x_i\le n)$, indicating the index of the modified element in the $i$-th sequence.

If the $i$-th sequence cannot be turned into a logarithmic sequence without modifying the already changed element, output `-1`. Otherwise, output the minimum number of elements that need to be changed.

Explanation for Sample $1$: Assume the initial sequence is $0,1,\pi,2,0.7,1+\pi$. If the fourth element is changed to $8$, then we can change the second element to $4$ and the sixth element to $4+\pi$. The sequence becomes $0,4,\pi,8,0.7,4+\pi$, which is a logarithmic sequence again. |Subtask ID|Additional Constraints|Score| |:-:|:-:|:-:| |$0$|Sample only|$0$| |$1$|$n\le 20,q\le 20$|$17$| |$2$|$q\le 8$|$24$| |$3$|$n\le 10^4$|$26$| |$4$|No additional constraints|$33$| Translated by ChatGPT 5