PROBLEM LINK:
Author: Devanshu Agarwal
Tester: Michael Nematollahi
Editorialist: Hussain Kara Fallah
PREREQUISITES:
Elementary Number Theory:
Euler Totient function, Primitive Roots, Fermat Little Theorem.
DIFFICULTY:
Medium - Hard
PROBLEM:
Recently, Chef has moved to an evil land. In this land, there is only one bank, which offers N savings plans (numbered 1 through N).
Initially, Chef 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 Chef chooses the i_{th} savings plan, the number of coins in his bank account gets multiplied by the interest factor P_i of this plan (whenever he chooses this plan again, the number of coins is multiplied by P_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 Chef 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
Constraints:
- 1≤N≤10^4
- 1≤M≤2⋅10^5
- M is a prime number
- 0≤F<M
- 0≤Pi<M
- F≠1
EXPLANATION:
This problem requires a good understanding of many topics in number theory. They won’t be covered in this tutorial. Here I will be using definitions and results of some theorems in the solution without formal proofs. To find out the proofs you need to explore these topics yourself. Here are some links to good resources.
Fermat Little Theorem
Euler Totient
Primitive Roots
Let’s revise the definition of a primitive root.
In modular arithmetic, 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 P as a power of this primitive root R.
Formally speaking, let’s replace each element in array P : P_i = f(P_i) such that R^{f(P_i)}≡P_i\, (mod \, M).
In this case let’s suppose we picked a set of T plans \{X_1,X_2,X_3,...,X_T\}, then:
X_1*X_2*X_3*....*X_T ≡ R^{f(X_1)+f(X_2)+f(X_3)+...+f(X_T)}
According to Fermal Little Theorem if M is prime then:
a^M≡a \,\,\,\,\,(mod\,\, M)
a^x≡a^{x\, \, mod \, \, (M-1)} \,\,\,\,\,(mod\,\, M)
Let’s now state a fact:
For a set S:
{\displaystyle \prod_{x}^{x \in S} x}≡G \,\,\,\, (modulo \,M) if and only if {\displaystyle \sum_{x}^{x \in S} f(x)}≡f(G) \,\,\,\, (modulo \,M-1)
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). F here represents the banned number.
We need to remove the minimum number of elements from our array P such that gcd(elements \, in \, P) is not divisible by f(F).
This is a well known problem that can be proved with Extended GCD algorithm. The main observation here is that for any element x in the transformed array P you can always take x which represents the original number or -x which represents the modular inverse (which always exists because M is prime).
So let’s fix our final GCD of the array let’s call it G_t and for each possible value we count all multiples of G_t so we keep them in array and remove rest of elements. After examining all possible values of G_t we take best choice.
We should pay attention to the case where F=0 where we should remove all zeroes from array.
Complexity: O(M \, log M)