Задача A.
В этой задаче требовалось лишь провести эмуляцию ходов блохи достаточное количество раз. Действительно, после 2n шагов блоха переместится на 1 + 2 + ... + 2n = n(2n + 1) кочек по часовой стрелке, то есть вернется в исходную позицию. Более того, следующие ее прыжки будут такими же как в начале, так как 2n ≡ 0(modn). Поэтому после 2n прыжков блоха не посетит никакие новые кочки. Таким образом, достаточно проэмулировать первые 2n шагов и проверить посещены ли все кочки.
На самом деле, нетрудно доказать, что блоха посетит все кочки в точности тогда, когда n --- степень двойки и получить альтернативное решение. Например, такое: printf("%s", n&(n-1) : "NO" ? "YES");
If n isn't a power of two, then n is divisible by some odd prime p. Let's look at hassocks not mod n, but mod p. We will see that not all residues (mod p) will be visited. Indeed after p jumps flea returns to initial residue mod p, because
Наоборот же
n&(n-1) : "NO" ? "YES"