How to solve this problem?

editorial
, ,
1

Probelm Code:SEQUA

Hi, I have recently found this question on a contest which has been ended? the editorial was unavailable, Plz share the techniques to solve this problem.
Link:Here

2

Please search the forum for similar questions. This has already been answered here:

https://discuss.codechef.com/questions/106804/can-someone-provide-me-solution-of-suhana-and-equation

1 Like
3

You probably know that one can calculate the power of a number in logarithmic time. You can also do so for calculating the sum of the geometric series. Since it holds that

1 + a + a^2 + … + a^(2*n+1) = (1 + a) * (1 + (a^2) + (a^2)^2 + … + (a^2)^n),
you can recursively calculate the geometric series on the right hand to get the result.

This way you do not need division, so you can take the remainder of the sum (and of intermediate results) modulo any number you want.
algo:-
geometricSeriesMod[a_, n_, m_] :=
Module[ {q = a, exp = n, factor = 1, sum = 0, temp},

While[And[exp > 0, q != 0],
If[EvenQ[exp],
temp = Mod[factor*PowerMod[q, exp, m], m];
sum = Mod[sum + temp, m];
exp–];
factor = Mod[Mod[1 + q, m]factor, m];
q = Mod[qq, m];
exp = Floor[ exp /2];
];

Return [Mod[sum + factor, m]]
]
Parameters:

a is the “ratio” of the series. It can be any integer (including zero and negative values).
n is the highest exponent of the series. Allowed are integers >= 0.
m is the integer modulus != 0

my code:-CodeChef: Practical coding for everyone

1 Like
4

Can you please delete your answer and post it in the link that I’ve provided.
This way all the explanations of this problem will be in the same place.