Editorial for COCI '09 Contest 3 #6 Planete
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
With we denote that divides , i.e. there exists such that .
Let us denote with duration of events in days. Note that saying:
- "Between dates and there were events , events , etc."
is the same as saying:
- "".
where is the difference in days between dates and . Further, we can split that into:
- ""
- ""
(note that ). Since and are prime numbers, using Gaussian elimination, we can find all possible remainders of 's when divided by and (separately). Using the Chinese remainder theorem, we can further determine the remainder of each when divided by .
Comments