# How to solve this problem?

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.

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

1 Like

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[q
q, 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

1 Like