AMR15B - Editorial

PROBLEM LINK

Practice
Contest

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<int> 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

Answer = \bigg(\prod_{{x \in [1, 10^5]}}{x^{S_x}}\bigg) \% 10^9+7

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))

SIMILIAR PROBLEMS

Bokam and his gcd

Multipliers

Coprime Triples

2 Likes

Shouldn’t it be for(auto it: div[x]) F[it]++; ???

2 Likes

Please provide the editorialist’s solution.

Where is editorialist solution?

2 Likes