# 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

*such that*

**x***.*

**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+(2*P) , …L + ((K-1)*P)**being the minimum value of*

**L***such that*

**x***and*

**A^x \equiv C \pmod{M}***being the cycle length after which the mod repeats itself . Now, We can easily find the sum of this AP .*

**P**# 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**

**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

*be two integers .*

**b**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) )