PROBLEM LINK
Panel Members
Problem Setter: Suhash
Problem Tester:
Editorialist: Sunny Aggarwal
Contest Admin:
Russian Translator:
Mandarin Translator:
Vietnamese Translator:
Language Verifier:
DIFFICULTY:
Medium
PREREQUISITES:
Fermat little theorem, Number Theory, Subset Theory, Mathematics.
PROBLEM:
Given an array A consisting of N integers where, each value A_i \le 10^5. We are asked to calculate the product of gcd of all non empty subset of array A modulo 10^9 + 7.
EXPLANATION
Let us solve the following simpler problem first in order to understand the solution of original problem better.
Problem Statement
Given an array A consisting of N integers where, each value A_i \le 10^5. For each number i where i \in (1, 10^5), calculate the number of non empty subsets with gcd = i modulo 10^9 + 7.
Lets create an array S[] where S_i will contain the number of non empty subsets with gcd = i and an array F[] where F_i will contain the number of elements among given N elements that are multiple of i.
How to construct array F ?
It is given that each value in the array A i.e A_i \le 10^5. Therefore, we can simply pre compute the divisors for a given i where i \in [1, 10^5] and use following algorithm to fill array F.
C ++ Code
vector div[ 100000 ];
void pre() {
for(int i=1; i<=100000; i++) {
int j = i;
while( j <= 100000 ) {
div[j].push_back( i );
j += i;
}
}
}
int F[100000];
void solve() {
int n;
cin >> n;
for(int i=1; i<=n; i++) {
int x;
cin >> x;
for( auto it: P[x] ) {
F[it] ++;
}
}
}
F_x stores the count of numbers which are multiple of x. Therefore, choosing any non empty subset of these numbers will produce gcd of any of these kind x, 2*x, 3*x … and so on ( multiples of x ) and if we know how many subsets are there which produces gcd = 2*x, 3*x, 4*x … and so on in advance, we can evaluate the number of subsets with gcd = x easily.
Above explanation is easy to understand with the following code.
void solve() {
for(int i=100000; i>=1; i--) {
int remove = 0;
int j = 2 * i;
while( j <= 100000 ) {
remove += S[j];
remove %= mod;
j += i;
}
int total = (power(2, F[i]) - 1); // number of non empty subsets
S[i] = total - remove; // removing subsets with gcd 2 * i, 3 * i...
if( S[i] < 0 ) {
S[i] += mod;
}
}
}
Hurray !! We have solved the simpler version of our original problem.
At this point, we know for each value x \in [1, 10^5], the number of subsets with gcd = x in S_x and our original problem asked for the following expression
Note that if a given x can’t be gcd of any subset, then S_x = 0 and therefore it is correct to write above expression.
How to compute above expression ?
We cannot compute this expression easily as value of S_x can be very large. So, we will be using Fermat Little Theorem here. Fermat’s Little theorem states that a^{p-1} = 1 mod p. Where p is prime. This is valid for all integers a. So if we want to calculate a^b mod ( p ) and b = k * (p-1) + m. Then we know a^b = (a^{p-1})^k * a^m = 1^k * a^m = a^m and therefore, we will be maintaining array S[] modulo (10^9 + 6) instead.
Please have a look at editorialist’s solution for implementation details.
COMPLEXITY
O(T*max(A_i) * \log(A_i))