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

Please tell why this does not work? since going by the fermat’s theorem, whenever I need to calculate a^b %p such that (b>>1) then we do a^(b%(p-1)) %p. I have attached a code also which proves that bin(a,b%(mod-1),mod) is same as bin(a,b,mod), but bin(a,b,mod-1) gives different result.

**fermat's th.**

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll mul(ll a,ll b,ll mod){
    return ((a%mod)*(b%mod))%mod;
}
ll bin(ll a,ll b, ll mod){
    ll res=1;
    while(b){
		if(b&1){ res=mul(res,a,mod);}
        a=mul(a,a,mod);
        b>>=1;
    }
    return res%mod;
}
int main() {
    // we want 2^10 %7

    ll ans=bin(2,10,7-1);
    ll ans2=bin(2,10%(7-1),7);
    ll ans3=bin(2,10,7);
    cout<<"ans1 = "<<ans<<endl<<"ans2 = "<<ans2<<endl<<"ans3 = "<<ans3;
}

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
ll freq[100100], cnt[100100];
const int mod=1e9+7;

ll mul(ll a,ll b,ll mod=1e9+7){
    return ((a%mod)*(b%mod))%mod;
}
ll bin(ll a,ll b, ll mod=1e9+7){
    ll res=1;
    while(b){
		if(b&1){ res=mul(res,a,mod);}
        a=mul(a,a,mod);
        b>>=1;
    }
    return res%mod;
}

void solve(){
    memset(freq,0,sizeof(freq)); memset(cnt,0,sizeof(cnt));
    int n; cin>>n; 

    for(int i=0;i<n;i++){
        int x; cin>>x;
    	freq[x]++;
    }
    
    freq[1]=n;
    for(int i=2;i<=n;i++){
        for(int j=i+i;j<=n;j+=i){
            freq[i]+=freq[j];
        }
    }

    cnt[1]=n;
    for(int i=1;i<=n;i++){
        cnt[i]=(bin(2LL,(freq[i]%(mod-1)))-1)%mod;
        if(cnt[i]<0) cnt[i]+=mod;
    }

	for(int i=n;i>0;i--){
        for(int j=2*i;j<=n;j+=i){
            cnt[i]=((cnt[i]-cnt[j])%mod+mod)%mod;
        }
    }    

    ll ans=1;
    for(int i=1;i<=n;i++){
        ans=mul(ans,bin(i,cnt[i]%(mod-1)));
    }
    cout<<ans<<endl;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t; cin>>t; while(t--)
    solve();
}