Discount on Dishes
All submissions for this problem are available.
Chef Polo has opened up a new restaurant. He wants to make it as much popular as he can. Chef has M dishes to serve (numbered from 0 to M-1).
To make his restaurant popular he wants to give discount everyday for a dish. But he has not been able to decide which dish should be discounted on a particular day. So he takes help from
his friend Palin. Palin has come up with a unique algorithm
He has choosen 3 secret numbers, A,B,C to start with
His unique algorithm says:
On day 1 choose dish no. A.
(Now keep track of day numbers.)
Now on nth day: suppose dish chosen on day n-1 was K
If n is even, choose (K+B)th dish
otherwise, choose (K*C)th dish
Offcourse he will take MOD of dish number thus found with M (because he has only M dishes)
If A=5, B=3, C=2, M=20
Then dishes chosen for first 5 days will be 5,8,16,19,18
Chef Polo is too much curious about future
so he wants to know which dish will be discounted on nth day. But he is busy with preparing
the dishes So he wants your help.
first line contains T, the no of test cases
Each of next T lines contains 5 integers A,B,C,n,M
For every testcase the only line should contain single integer, answer to the problem
- 1 ≤ T ≤ 10^4
- 1 ≤ A,B,C,n,M ≤ 10^9
- A < M
Input: 2 1 2 3 4 5 6 7 8 9 10 Output: 1 6
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.