# PROBLEM LINK:

* Author:* Himanshu

# DIFFICULTY:

EASY

# PREREQUISITES:

Modular Exponentiation, Arithmetic progression

# PROBLEM:

Given two AP’s in which the first element of both the AP’s are the same. You need to find the number of common elements between these two given AP’s.

# EXPLANATION:

Since the first element of both the arrays is the same. Let it be a.

common difference of first array = m

common difference of second array = n

general term for first AP:- a + x * m , where 0 <= x <= (p-1)

general term for second AP:- a + x * n , where 0 <= x <= (q-1)

The common elements will themselves form an AP. The common difference for the new AP will be the lcm of the common differences of the given two APs.

d = lcm(m, n)

Now the last term of this AP will be less than or equal to the min of the last terms of the two given APs.

x = min(last term of arr, last term of brr)

Now you need to find no. of common terms say N

a +(N-1)*d <= x

Solve the above equation to find N

### COMPLEXITY:

O(log min(m, n))(log min(m, n)) for gcd