omg tourist round

LJC00118 will win IOI2023!

\ hehezhou / \ hehezhou / \ hehezhou /

Here I've got a solution to problem F without hashing or any other randomicity. Though I don't know how to prove it, it seems to be correct. Due to the limitation of the space, I'll only put the conclusions here.

First if $$$ n = 1 $$$, the answer subset include only $$$ 1 $$$. Now we assume $$$ n \not = 1 $$$.

If $$$ n \equiv 1 \pmod 2 $$$, we check if $$$ n \cdot (\frac{n - 1}{2} - 1) $$$ is a square number. If so, the answer subset is all numbers from $$$ 1 $$$ to $$$ n $$$ except $$$ \frac{n - 1}{2} - 2 $$$ and $$$ n - 2 $$$.

If $$$ n \cdot (\frac{n - 1}{2} - 1) $$$ is not a square number, $$$ n $$$ will not be in the answer subset, and we let $$$ n \leftarrow n - 1 $$$ and continue our discussion.

So we now have $$$ n \equiv 0 \pmod 2 $$$. Let $$$ m = \frac{n}{2} $$$.

If $$$ m \equiv 0 \pmod 2 $$$, the answer is $$$ 1, \cdots, n $$$ except $$$ m $$$.

Else we have $$$ m \equiv 1 \pmod 2 $$$. Check if $$$ \frac{m + 1}{2} $$$ is a square number. If so, answer is $$$ 1, \cdots, n $$$ except $$$ m + 1 $$$.

We also check if $$$ m = 9 $$$. If $$$ m = 9 $$$, answer is $$$ 1, \cdots, n $$$ except $$$ 7 $$$.

In the case that neither $$$ \frac{m + 1}{2} $$$ is a square number nor $$$ m = 9 $$$, answer is $$$ 1, \cdots, n $$$ except $$$ 2 $$$ and $$$ m $$$.

Obviously there must be $$$ \text{answer's size} \geqslant n - 3 $$$, for there will be at most $$$ 2 $$$ absent number for even $$$ n $$$ and one more for odd $$$ n $$$.

Check 140891764 for code. I use this OEIS sequence to reach some of the same conclusion as in the official solution.

As you see, this solution is partly based on the official solution, but to construct the subset by just discussing about $$$ n $$$, instead of using hashing.

Just because he is Karry5307

Fine. Thanks a lot.

I got WA on test 3 of problem F, but the judger said wrong answer The answer is wrong! (test case 300). However it is guaranteed that $$$ t \leqslant 20 $$$ and the value $$$ t $$$ of test 3 is $$$ 20 $$$. Also I can pass data of test 3 on my own PC.

What's the meaning of the judger's comment?

Consider each prime factor $$$ p $$$ of $$$ k $$$. Assume that the prime $$$ p $$$ appears $$$ x $$$ time(s) in the factorization of $$$ k $$$ ($$$ p^x | k, p^{x + 1} \not| k $$$), appears $$$ y $$$ time(s) in $$$ A $$$'s and $$$ z $$$ time(s) in $$$ B $$$'s.

Since $$$ \gcd(A, B) = 1 $$$, either $$$ y $$$ or $$$ z $$$ must be equal to $$$ 0 $$$ (otherwise $$$ p|A, p|B, p|\gcd(A, B) $$$). Also we have $$$ y + z = x $$$ for $$$ AB = k $$$.

So there are just $$$ 2 $$$ possibilities: $$$ y = 0, z = x $$$ or $$$ y = x, z = 0 $$$. Because $$$ p $$$ is one of the prime factors of $$$ k $$$, $$$ x \gt 0 $$$ holds. Therefore, the $$$ 2 $$$ situations are definitely different.

For each prime factor there are $$$ 2 $$$ possibilities to "assign" it to $$$ A $$$ or $$$ B $$$. Apparently the situation of one prime factor is independent of others. So simply multiply them all and the answer is $$$ 2^{\text{number of prime divisors of k}} $$$.