Winter Cup 6.0 Online Mirror Contest |
---|
Finished |
In the modular universe, everything is modular, even coordinates!
For example, if someone has coordinates $$$(x,y)$$$ in the normal universe, they will have coordinates $$$(x \bmod n,y\bmod m)$$$ in some modular universe, where $$$(n,m)$$$ is the modularity of that universe.
Now, $$$n\times m$$$ people live in the $$$(n,m)$$$-modular universe. They are usually found at different positions in the universe, but there is always a day called the singularity day, where all the population will gather at the same coordinate $$$(0,0).$$$ This is a very special holiday as only singularity days have this property.
Once the singularity day finishes, for each $$$k\in\{0,\dots,nm-1\},$$$ the $$$k^\text{th}$$$ person will go to the point $$$\left((k \ \text{div} \ m ) \bmod n, k\bmod m\right)$$$ on the next day, and from there on, that person will continue their journey to $$$((2k \ \text{div} \ m) \bmod n, 2k\bmod m),((3k \ \text{div} \ m) \bmod n, 3k\bmod m),\text{etc}\dots$$$ in the subsequent days.
Now, the most important phenomenon in history is the modular big bang, which is the only day in history on which all modular universes have a singularity day at the same moment.
You are from universe $$$(0,0),$$$ where you don't have modular coordinates, and you are asked to inquire more intel about the patterns of universe $$$(n,m).$$$ You will do that by inspecting the number of people residing in the same point $$$(x,y)$$$ during some day $$$d.$$$
Your supervisors shared with you some important intel, which is the day on which the modular big bang occurred.In fact, it is denoted as day $$$0$$$ by your agency's convention. They sent you also $$$Q$$$ queries, where each one is of the form '$$$\mathtt{n\ m\ x\ y\ d}$$$'. For each one of these queries, you have to find the number of people residing in point $$$(x,y)$$$ on day $$$d$$$ in the $$$(n,m)$$$-modular universe. Good luck with that!
For each query, output one integer $$$r$$$ denoting the number of persons residing at position $$$(x,y)$$$ during day $$$d$$$ in the universe $$$(n,m).$$$
51 1 0 0 12 2 0 0 110 20 0 0 3010 20 3 1 1610 20 0 0 5
1 1 100 0 25
In the queries, the time is represented with respect to the modular Big Bang. In fact, day $$$d$$$ means $$$d$$$ days since the Big Bang. In particular, day $$$0$$$ is the day of the modular Big Bang.
Name |
---|