Ninja in Evil Land

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 :

1. Declare two arrays, ‘revPower’ and ‘cnt’ which will used to get our transformed array from function ‘f’.
2. Initialize all values in ‘revPower’ to -1 and ‘cnt’ to 0.
3. Get the primitive root of ‘M’ and store it in ‘root’.
4. Declare a variable ‘curr’ which will be used to get powers of root. Mark ‘revPower[curr]’ as 0.
5. First we check for our special case.
6. If ‘F’ is 0:
   • Count zeroes in ‘ARR’
   • Return the count of zeroes.
7. Declare ‘j’ and initialize it to 1
8. 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
9. Now transform array elements according to our function ‘f’.
10. 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
11. Transform ‘F’ i.e. ‘F’ = revPower[F], ‘F’ %= (M - 1).
12. Declare a variable ‘ans’ which will store the maximum elements that can remain in ‘ARR’.
13. Declare an array ‘divisors’ to store all divisors of M - 1.
14. for ‘j’ in [1, .. M - 1]:
    • if (M - 1) % j is 0:
      • divisors.push(j)
15. 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)
16. Finally return ‘N’ - ‘ans’.

O( N + ( M * log( M ) ) ), where ‘N’ and ‘M’ are the number of Plans, Modulo number repectively.
 

For finding the root of ‘M’, ~M * (log( M ) ) time is required. And while transforming array we require ~N time.

Hence the time complexity is O( N + M*log(M) ).

O( M ), where ‘M’ is the number of Plans.
 

We are using ‘revPower’ and ‘cnt’ arrays.

Hence the space complexity is O( M ).