# PROBLEM LINK

Practice**Author:** Mann Mehta

**Tester:** Jaymeet Mehta

**Editorialist:** Vatsal Parmar

# DIFFICULTY

Easy

# PREREQUISITES

Basic Math, Modulo Operations, Prime Algorithms, Factorisation, Observation

# PROBLEM

You have given an integer N denotes Matrix Mat[N][N], where N \times N should have exactly 3-Factors. Here you also given a integer K, we have to calculate the number of occurrence of integer K in Mat[N][N] where every mat[i][j] element have value (i \times j) modulo N.

# EXPLANATION

**Solution-1 (Brute Force Approach): -**

Factorize N and count the number of factor’s of N^2. If it count to 3 factor’s then go for next step where you have to construct 2-D mat[N][N], where every mat[i][j] = ((i+1) \times (j+1)) modulo N. Considering index from 0 to N-1.

After that count the number of times that K occur in the Filled Matrix.

Now this is O(N^3) Complexity where Optimization require to get AC.

**Solution-2: -**

All prime number’s have exactly 2 factors, but when we are talking about it’s square it have exactly 3 factor's, that are 1, P, P^2. where P is Prime Number.

Now, To check whether the number is prime or not. We have different methods to check.

**Iterate all the number from 2 to N-1 and check if number divides N or not***School Method*-
**Iterate all the from 2 to \sqrt N and check if number divide N or not***Optimize School Method*. Instead of checking till n, we can check till vn because a larger factor of n must be a multiple of smaller factor that has been already checked

**Sieve of Eratosthenes**

Now, you have to check the occurrence of K in the filled matrix, here you don’t have to fill the entire Matrix instead you require basic math and observation to reach the optimize solution.

When we observe carefully we will find out that in N × N matrix where N is prime Number, then any number between 1 to N-1 occur’s exactly (N-1) times and 0 occurs exactly 2N − 1 times.

**N × N = (N-1) × (N-1) + 2N − 1
N × N = N^2 − 2N + 1 + 2N − 1
N × N = N^2**

**Here we conclude that matrix contain only number from 0 to N-1.**

**also A modulo N give value in range (0 to N-1 only)**

# TIME COMPLEXITY

Time Complexity is depend on the which method is use to check the number is prime or Not.

- Sieve of Eratosthenes O(N) over all test cases. Here (max(N) is 10^5)
- Optimize School Method O(√N) per each test case.

**School Method give TLE verdict !!!**