The problem was kindly provided by Vladimir V. Zelevinsky - many thanks!
CodeAbbey is located on the edge of the beautiful Miller Park. On a normal day, you'd enjoy the park's many varieties of trees as you wander down its shady alleys.
Not, however, today. This morning, the Head Abbot asked you to perform a daunting task: to count every leaf on every tree in the park. Moreover, he asked you to do this separately for each variety of tree.
This problem has two interesting wrinkles. One makes your task much easier. Another one makes it a little bit harder.
The Abbey has been taking care of the park for centuries and by now has discovered a way to determine the exact number of leaves on each particular tree. It so happens that the leaf counts match the outputs of a simplified version of a pseudorandom Linear Congruential Generator. Here's how it works.
A particular tree variety is associated with two numbers, A and M. To seed the generator, you assign the value of 1 to the variable X. Then you compute the following expression:
X := (X * A) % M
In other words, you multiply the current value of X by A, take that result modulo M, and assign it back to the variable X. That value is how many leaves are there on the first tree of this variety. To compute the number of leaves on the second tree of the same variety, you repeat the same computation using the current value of X. Repeat the process as many times as you need to.
Let's provide a detailed example. Suppose there are T = 5 trees in the park of the variety described by
A = 6 and M = 13. Setting the seed X to 1, we perform the same computation five times:
X = 1
X1 = (X * 6) % 13 = (1 * 6) % 13 = 6
X2 = (X1 * 6) % 13 = (6 * 6) % 13 = 10
X3 = (X2 * 6) % 13 = (10 * 6) % 13 = 8
X4 = (X3 * 6) % 13 = (8 * 6) % 13 = 9
X5 = (X4 * 6) % 13 = (9 * 6) % 13 = 2
This means that the five trees of this variety have correspondingly 6, 10, 8, 9, and 2 leaves, and
the total for this variety is 6 + 10 + 8 + 9 + 2= 35.
The input data is provided in the following format. The first line has a single number N: the number of
tree varieties. Each subsequent line, N of them in total, has three numbers: A (the multiplicative factor),
M (the modulus), and T (the number of trees of this variety).
N
A1 M1 T1
A2 M2 T2
...
AN MN TN
The answer should be N space-separated values: the total number of leaves for each variety of tree.
Oh, and the second wrinkle? Miller Park is vast. Enormous. Immense. Whatever you're thinking of, it's bigger than that. Much bigger.
Examples:
input data:
2
6 13 5
7 11 10
answer:
35 55
input data:
13
1824 4657 7
3663 3833 70
3112 5231 597
7699 7907 4425
3027 4877 43751
7453 9151 312145
1280 2213 2713081
5925 7499 21985893
4042 9473 202358677
4404 8111 1717105499
4708 9887 13218699779
7781 8363 414402445760
5398 6007 9549831875808
answer (wrapped for convenience):
10746 127468 1561740 17442952 106685040 1428234129 3002021590 82436076789
958471937683 6963721414786 65346642316466 1732823826985397 28682920039044874