AMCS04 - Editorial

PROBLEM LINK

Contest
Practice

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

RELATED PROBLEMS

Discrete Logarithm
Fibonacci

SOLUTION

Implementation in C++

3 Likes