PROBLEM LINK: Practice, Contest
CATEGORY: EASY-MEDIUM
PRE-REQUISITES: Modulo Concepts.
PROBLEM:
You need to solve the A.G.P :
\left \{ \sum_{i=0}^{n}\left ( \left [ a+i\cdot d \right ] \cdot x^{n-i}\right ) \right \} mod \ 215372682525
EXPLAINATION:
It is a simple mathematics question. Here, you need to calculate the sum mod 215372682525 as mentioned above. But, keep in mind that 215372682525^2 = 46385392378014440375625, which is greater than 2^64. Therefore, all you need to do is calculate the value of x^0, x^1, x^2, x^3, x^4, …, x^n and simultaneously take the mod with 215372682525 and save the mod value at corresponding index i. Similarly, do the same for a + id for each value of i and save the mod value at corresponding index i. Now, multiply a + id with the corresponding x^(n-i) value and take the mod and save the mod value at corresponding index i. Finally, add them and simultaneously take the mod.
C++ CODE:
Link
Author: Suraj Singh
Tester: Naman Taneja
Editorialist: Suraj Singh