PROBLEM LINK
Author : Ajay Krishna
Editorialist : Abhay Garg
DIFFICULTY
Medium
PRE-REQUISITES
Modular Exponentiation , Maths , Meet-in-the-Middle
PROBLEM
Given A,M,C,K ( ‘A’ and ‘M’ are co-prime) , We need to find the sum of the first k values of x such that A^x \equiv C \pmod{M} .
QUICK EXPLANATION
The values of x will be in an Arithmetic Progression of the form L , L+P , L+(2P) , …L + ((K-1)P) , L being the minimum value of x such that A^x \equiv C \pmod{M} and P being the cycle length after which the mod repeats itself . Now, We can easily find the sum of this AP .
EXPLANATION
The problem can be divided into two steps :
1.Finding the minimum value L such that A^L \equiv C \pmod{M}.
2.Finding the cycle length.
Finding the minimum value L
We can easily find an L such that A^L \equiv C \pmod{M} in O(M) time , but , that would be TLE.
So , Here we use the concept of Baby-Step Giant-step .
We know that L < M .
Let a and b be two integers .
Now L would be of the form,
L = ( a * \sqrt[]{M} ) + b
a , b being less than equal to \sqrt[]{M}.
Now,
A^L \equiv C \pmod{M}
A^{ a*\sqrt[]{M}\ } * A^b \equiv C \pmod{M}
A^{ a*\sqrt[]{M}\ } \equiv C * A^{-b} \pmod{M}
This is known as Meet-in-The-Middle concept .
Now , We can easily find the first \sqrt[]{M} values of (C*A^{-b}) Mod M ( for each b<\sqrt[]{M} ) and store them in a map using Modular Exponentiation . The above map will give us the minimum value x(if there exists such a value) such that A^x \equiv i \pmod{M} for each ‘i’.
Note : You can calculate A^{-b} \pmod{M} using this.
This can be done in O(\sqrt[]{M} log M) . ( O(\sqrt[]{M}) for \sqrt[]{M} values of b
and O( log M ) for computing each A^{-b} using modular exponentiation.
Now , For all \sqrt[]{M} value of a , compute (A^{a*\sqrt[]{M}}) Mod M and find whether there exists any value of C*A^{-b} in the map computed above , If Yes , then find that value using map[ A^{a*\sqrt[]{M}} \pmod{M} ] and compute the minimum L where L= (a*\sqrt[]{M}) + b.
Thus, we can find the minimum value of L in O( \sqrt[]{M} log(M) ) time.
Finding the Modular Cycle Length
Modular Cycle Length is defined as the minimum value x such that A^{x+y} \equiv A^y \pmod{M} for any y.This means we have to find the minimum value of x such that A^x \equiv 1 \pmod{M} such that x>0.
This can be done by two methods.
First
Find minimum value of L such that A^L \equiv 1 \pmod{M} and L>0 by the above described Baby-Step Giant-Step method.
Second
We know that A and M are co-prime,
This means that A^{\varphi{(M)}} \equiv 1 \pmod{M} . [ This is because of the Euler’s Theorem ]
Now , The minimum value of x such that A^x \equiv 1 \pmod{M} will be a factor of \varphi{(M)} because we can express \varphi{(M)} as k*x for some x.
So, We can find the minimum factor x of \varphi{(M)} such that A^x \equiv 1 \pmod{M} by iterating through all the factors of \varphi{(M)}.
CLAIM :
The smallest value of x(x>0) such that A^x \equiv 1 \pmod{M} divides \varphi{(M)} .
PROOF :
Let \varphi{(M)} = q \cdot x + r , where r < x .
Now , We know that A^x \equiv 1 \pmod{M} , so , this means that A^{x \cdot q} \equiv 1 \pmod{M} .
We also know that A^{ x \cdot q + r} \equiv 1\pmod{M}.
So, this means A^r \equiv 1 \pmod{M} .
Now, r < x and x is the smallest positive value such that A^x \equiv 1\pmod{M}.
So, this means r=0.
So, \varphi{(M)} = q \cdot x.
So, x is a factor of \varphi{(M)}.
So, this can be done in O( \sqrt[]{M} * log(M) ) . [ O( \sqrt[]{M} ) for each factor of \varphi{(M)} and O( log(M) ) for calculating each A^x \pmod{M} for each factor x of \varphi{(M)}.
This concept is generally known as Meet-in-the-Middle.
Now , We have computed L and P and we need to find the sum of an AP of the form L , L + P , L + 2P ,… L + (K-1)P .
Note : The answer is the sum of an AP because if A^x \equiv C \pmod{M} , then the next value of y such that A^y \equiv C \pmod{M} will be x+P because P is the smallest value such that A^P \equiv 1 \pmod{M}.
Thus , Ans = (K/2)*( (2*L) + ((K-1)*P) )
Time Complexity
O( \sqrt[]{M} * log(M) )
Space Complexity
O( \sqrt(M) )