P2942 [USACO09MAR] Moon Mooing G

A full moon casts some sort of spell on the cows and, like their cousins the wolves and coyotes, they bay at the moon — mooing instead of howling, of course. Each "moo" lasts a certain amount of time. A short "moo" might last time 1; a longer one might last time 24 or even 1,000,000,000 or longer (cows can really moo when they want to). No "moo" will last more than or equal to $2^{63}$. It should come as no surprise that the cows have a pattern to their moos. Bessie will choose an integer $c$ ($1 \le c \le 100$) that is the initial length of a moo. After Bessie moos for length $c$, the cows calculate times for subsequent moos. They apply two formulae to each moo time to yield even more moo times. The two formulae are: ```cpp f1(c)=a1*c/d1+b1 (integer divide, of course) and f2(c)=a2*c/d2+b2. They then successively use the two new times created by evaluating f1(c) and f2(c) to create even more mooing times. They keep a sorted list of all the possible mooing times (discarding duplicates). They are allowed to moo a total of N times (1 65 The tenth time is 65, which would be the proper answer for this set of inputs. ``` They keep a sorted list of all possible moo times (discarding duplicates). They are allowed to moo a total of $N$ times ($1 \le N \le 4{,}000{,}000$). Please determine the length of the $N$-th moo. The constants in the formulae are integers and satisfy: $1 \le d_1 < a_1 \le 20$; $0 \le b_1 \le 20$; $1 \le d_2 < a_2 \le 20$; $0 \le b_2 \le 20$. The two formulae are: $f_1(c)=\lfloor a_1 c / d_1 \rfloor + b_1$ $f_2(c)=\lfloor a_2 c / d_2 \rfloor + b_2$.

- Line 1: Two space-separated integers: $c$ and $N$. - Line 2: Three space-separated integers: $a_1$, $b_1$, and $d_1$. - Line 3: Three space-separated integers: $a_2$, $b_2$, and $d_2$.

- Line 1: A single integer — the length of the $N$-th moo.

Translated by ChatGPT 5