Last Updated: 10 Feb, 2022

Ninja in Evil Land

Hard

Solve now

Problem statement

Recently, Ninja has moved to an evil land. In this land, there is only one bank, which offers ‘N’ savings plans (numbered 1 through ‘N’). The interest factors are given in form of array ‘ARR’.

Initially, Ninja has 1 coin in his account. He may choose bank plans for as long as he wishes, in any order; each plan may be chosen any number of times. For each valid ‘i’, whenever Ninja chooses the i-th savings plan, the number of coins in his bank account gets multiplied by the interest factor ‘ARR[i]’ of this plan (whenever he chooses this plan again, the number of coins is multiplied by ‘ARR[i]’ again).

Since the bank in the evil land is evil, it always stores the number of coins in each account modulo ‘M’. (‘M’ is a prime number). You need to remove some (possibly none or all) plans in such a way that Ninja’s account may not ever contain an amount exactly equal to ‘F’ (which is given in input). Find the minimum number of plans you must remove.

For Example:

Let ‘N’ = 2, ‘M’ = 5, ‘F’ = 3 and ‘ARR’ = [2, 4].
Ninja’s account can contain 3 coins ((2 * 4) % 5 = 3), if he chooses Plan 1 and Plan 2. It is enough to remove Plan 1 as he can then only multiply the number of coins in his account by 4.

Input Format :

The first line contains an integer 'T', which denotes the number of test cases.

The next line contains three integers ‘N’, ‘M’ and ‘F’ denoting the number of Plans, Modulo number and coins which Ninja’s bank cannot contain.

The next line contains ‘N’ space-separated integers representing an array of interest factors.

Output Format :

For each test case, print the minimum number of plans you must remove.

Note :

You don't need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 ≤ T ≤ 10
1 ≤ N ≤ 5000
1 ≤ M ≤ 10000
0 ≤ F < M, F ≠ 1
0 ≤ ARR[i] < M

Time limit: 1 sec

Solve now

Approaches

01 Approach

The prerequisites to understand this approach are Euler Totient Function, Primitive root and Fermat little theorem.

Here I will be using definitions and results of some theorems in the solution without formal proofs. I have provided the links to these theorems you can go through them before proceeding.

First of all we pay attention to special case when ‘F’ is 0. In this case the answer will be number of zeroes in the array.

A number g is called a primitive root modulo n if every number coprime to n is congruent to the power of g modulo n. Mathematically, g is a primitive root modulo n if and only if for any integer x such that gcd(x,n) = 1, there exists an integer k such that:

g^k ≡ x (mod n)

Since our Modulo ‘M’ in this problem is prime then we can find a primitive root for it and write all numbers of array ‘ARR’ as a power of this primitive root R.

Formally speaking, let’s replace each element in array ARR : ARR[i] = f(ARR[i]) such that R^ARR[i] ≡ ARR[i] (mod M)

In this case let’s suppose we picked a set of ‘K’ plans {X₁, X₂, .. X_k,} then:

X₁ * X₂ * .. * X_k ≡ R^{f(x1) + f(x2) + .. + f(xk)}

According to Fermal Little Theorem if ‘M’ is prime then:

a^M ≡ a (mod M)

a^x ≡ a^{x mod (M - 1)} (mod M)

Now,

X₁ * X₂ * .. * X_k ≡ F(mod M) if and only if f(X₁) + f(X₂) + .. + f(X_k) = f(F)(mod (M - 1))

where ‘F’ is coins which Ninja’s bank cannot contain.

So after transforming the array with our function f we need to remove the minimum number of elements such that it’s impossible to form a multiset with the numbers such that the sum of this multiset’s elements is equal to f(F) (modulo M - 1).

We need to remove the minimum number of elements from our array ‘ARR’ such that gcd(elements in ARR) is not divisible by f(F).

So let’s fix our final GCD of the array let’s call it G_arr and for each possible value we count all multiples of G_arr so we keep them in array and remove rest of elements. After examining all possible values of G_arr we take best choice.

The steps are as follows :

Declare two arrays, ‘revPower’ and ‘cnt’ which will used to get our transformed array from function ‘f’.
Initialize all values in ‘revPower’ to -1 and ‘cnt’ to 0.
Get the primitive root of ‘M’ and store it in ‘root’.
Declare a variable ‘curr’ which will be used to get powers of root. Mark ‘revPower[curr]’ as 0.
First we check for our special case.
If ‘F’ is 0:
- Count zeroes in ‘ARR’
- Return the count of zeroes.
Declare ‘j’ and initialize it to 1
while True:
- Multiple curr by root
- Set curr as curr% M
- if revPower[curr] !is equal to -1:
  - Break,
- Set revPower[curr] as j
- Increase j by 1
Now transform array elements according to our function ‘f’.
for ‘i’ in [0, .. N - 1]:
- Set ‘ARR[i]’ as ‘revPower[ARR[i]]’
- Set ‘ARR[i]’ as ‘ARR[i]’ % ‘M’
- Increase cnt[ARR[i]] by 1
Transform ‘F’ i.e. ‘F’ = revPower[F], ‘F’ %= (M - 1).
Declare a variable ‘ans’ which will store the maximum elements that can remain in ‘ARR’.
Declare an array ‘divisors’ to store all divisors of M - 1.
for ‘j’ in [1, .. M - 1]:
- if (M - 1) % j is 0:
  - divisors.push(j)
for ‘d’ in ‘divisors’:
- if ‘F’ % d is 0:
  - Continue
- Declare ‘x’ as ‘cnt[0]’.
- for ‘i’ in [d, .. M]:
  - ‘x’ += cnt[i]
- ‘ans’ = max(ans, x)
Finally return ‘N’ - ‘ans’.

Solve now