Editorial for COCI '22 Contest 5 #3 Logaritam
Submitting an official solution before solving the problem yourself is a bannable offence.
Since , has to be equal to , so if the first element is changed the sequence cannot become logarithmic again. It is easily shown that for every pair of positive integers is equivalent to for positive integer . We conclude that logarithmic sequence is uniquely defined by values at prime indices. If the index of changed element is prime one possible way to "fix" the sequence is to change all of the elements at indices which are multiples of , there are of them. If that is the minimal number of changes necessary, then for any index of changed element the minimal number of changes necessary will be (since it is necessary to change at least one prime factor of ).
We will prove that is the solution and we can implement it with standard algorithm for finding prime factorization in .
Proof: Using induction by let's prove a stronger claim for odd primes : "Changing multiples of is the only minimal solution".
If is not divisible by the number of changes stays the same and the solution is unique.
If is divisible by then clearly the solution for needs to be expanded by changing the -th element and we get that is the least number of changes. Assuming that there exists another minimal solution that solution doesn't change the -th element and it is necessary to change another odd prime index (for it can be seperately shown it requires more than minimal changes) for which by induction hypothesis has unique solution for first element. Since is not divisible by that solution would have at least changes so it is not minimal.
For it doesn't necessarily hold that minimal solution is unique (for prime it is possible to change instead of ), however it still holds that the minimal number of changes necessary is . The proof similar to the previous is left for the reader as exercise as well as finding implementation which runs in time complexity of .