A. Gregor and Cryptography
Solution:
If P is an even number, just output 2 and P, so that the remainder is both 0. If P is an odd number, just output 2 and P-1, so that the remainder is both 1.
Code:
Java
C++
B. Gregor and the Pawn Game
Solution:
If the pawns can go directly to the end, then these pawns have priority to go directly to the end.
Then consider the pawn that has to eat an opponent pawn to reach the end. Consider the remaining pawns from left to right, and give priority to the opponent's pawn on the left.
Code:
Java
C++
C. Web of Lies
Solution:
If a noble has at least one noble friend who is bigger than him, then the noble will be killed sooner or later. Because nobles smaller than this noble will definitely be killed, and the next one will be this noble.
Therefore, we only need to count how many nobles have friends who are bigger than themselves.
Code:
Java
C++
D. Integers Have Friends
Solution:
If there are $a_i \bmod m = a_{i+1} \bmod m = \ldots = a_j \bmod m$, then there must be $(a_{i+1} - a_i) \bmod m = (a_{i+2} - a_{i+1}) \bmod m = \ldots = (a_j - a_{j-1}) \bmod m = 0$.
Let $d_i=a_{i+1}-a_i$. And if we want to verify whether there is such m in the interval from i to j, we only need to verify whether $\gcd(d_i, d_{i+1}, \ldots, d_{j-1})$ is not 1.
So we naturally thought of using the line segment tree to maintain the interval GCD. Then get the longest interval by enumerating i and j.
When we enumerate j, we don't need to re-enumerate from i every time, we can continue to enumerate following j based on the j left by the previous i.
Code:
Java
C++
