CHGCDG - Editorial

cook96
gcd
implementation
math
pre-process
sieve

#1

PROBLEM LINK:

Div1
Div2
Practice

Setter- Kirill Gulin
Tester- Ivan Safonov
Editorialist- Abhishek Pandey

DIFFICULTY:

EASY

PRE-REQUISITES:

Sieve of Erastothenes, Binary Search

PROBLEM:

Given an array A of N integers, we have to maximize the GCD of all elements of the array. To do that, you can select any array element A_i which is divisible by any number {d}^{2}, divide it by {d}^{2} and multiply any other array element by d.

QUICK EXPLANATION:

Key to AC- Realize that manipulation of powers of one prime is independent of powers of other primes. Perceiving that this question is more about manipulating prime and their powers rather than some complex mathematics theorem was important.

Make a list of primes, and smallest prime divisors of all numbers in range using sieve. Now, for each prime p_i, keep a note of how many array elements are divisible by it, and what is the power of p_i in their prime factorization form. Now whats left is finding what power of this prime can we maximum achieve in final answer using above operations - we can use BSH (Binary Search Heuristics) for this. Repeat for all primes and get an AC :).

EXPLANATION:

This editorial is divided into 2 sections. The first section will highlight on the pre-processing required, and the second section will feature how to calculate answers using Binary Search Heuristics (BSH).

Note that, I assume you all realize that, using operation of same number (i.e. dividing the same element by {d}^{2} and increasing it by d) is useless. It will just reduce the prime power of that prime, which we might want to maximize for GCD.

1. Pre-processing-

It seems kind of obvious that we might need factorization of elements. Also, usually such problems do involve manipulation of prime numbers. Hence the first step is to use sieve of erastothenes to pre-calculate-

  • Prime numbers in range [1,{10}^{6}]
  • The smallest prime factor of a given number. This ensures O(LogN) factorization of elements.

The observation to make is that manipulation of exponents of prime factors of A_i are independent. We can choose a prime d every time for our operation so that only the chosen prime gets affected. If this doesnt ring a bell, you can refer to tab below.

Click to view

Now, observe this thing by thinking in terms of prime numbers. You’d notice that, increasing or decreasing power of one prime by above operation has no effect on power of other primes. In other words, manipulation of primes is independent of one another. Changing exponent of one prime factor of A_i will have no effect on exponent of other prime factors if d is prime. Only the chosen prime power will get affected.

This is important as it helps in realizing that, increasing GCD prime by prime is the way to go. It gives an intuition that - “Ok, initialize GCD=1 for now. Lets pick a prime. Let me see what is the maximum possible power of it I can get for GCD of array using above operations. Multiply answer by it. Lets repeat this until we get answer.”

What is the next thing we need if we are to do such manipulations? We’d need the prime numbers and their exponents for all elements of array. I specifically liked the tester’s method of storing it (to use it later) and I think it can use some credit :slight_smile: .Its in tab below for reference.

Click to view
for (int i = 0; i < n; i++)
	{
		while (a* > 1)//Factorize a*
		{
			int p = mn[a*];
			int k = 0;
			while (a* % p == 0)
			{
				a* /= p;
				k++;
			}
			id[p].push_back(k);//Some array element as an exponent k for prime p.
		}
	}

This is especially nice because now you can also find how many array elements are divisible by p in O(1) time by idx[p].size().

2. Binary Search Heuristics-

I hope that the intuition so far, especially that of manipulating prime by prime, is clear to you.

Now, for each prime, we will Binary Search on the highest possible power achievable (of that prime) in the final GCD. It is actually quite simple.

Lets say we have to check if a power k is achievable for some prime p. How do we do it? Recall that using our operation, we can reduce the power of p in some A_i by 2 and increase power in another A_i by 1. In a way, its like “Sacrifice 2 powers of some A_i for 1 power in another element.” Since we aim to calculate Gcd, our aim is to maximize the minimum power p.

Now, we have to check if we can make exponent of p equal to k in GCD. Hence, it makes sense to calculate how much “excess exponent” of p can we take from "rich A_i", and how much exponent do we need to "poor A_i" to make exponent of p equal to k in GCD.

It can be elegantly done if you have pre-processed the exponents and primes like tester did. The tester used a vector idx[100001] where idx[p] had “Exponents of p which are >0 among all elements of array.” Hence, he can simply loop over idx[p] and calculate the excess and deficit exponents. (Do not forget that we are currently checking if we can achieve an exponent of k in GCD).

Now, things are quite simple. If we have gained sufficient exponent from "Rich A_i" to give to "Poor A_i", then a power of at least k is achievable in the final GCD. We check for the highest power achievable using binary search (proof in tab below).

Click to view

Say, we are checking for power k. Either we can achieve it, or we cannot achieve it. If we achieve it, we can discard checking for ALL powers in range [0,k-1] as if exponent k is achievable, then exponents <k are obviously achievable as well. If we cannot achieve k, then any exponent greater than k is also not achievable. Hence, the condition of Binary Search holds which allows its use.

The code to implement this is given below :slight_smile:

Click to view
for (int x : prime)//For all primes
		if (!id[x].empty()) // we can do operations for all primes independently, x - current prime
		{
			int l = 0;
			int r = 0;
			for (int k : id[x]) r = max(r, k + 1);//Find upper bound. r= Max exponent+1
			int num0 = n - id[x].size();//num0 = number of array elements with 0 exponent of x
			while (r - l > 1) // binary search for maximum possible power of x in answer
			{
				int h = (l + r) >> 1; // check x^h
				int now = 0;
				for (int k : id[x]) 
					if (k >= h)//Find excess power
						now += ((k - h) >> 1); // sum, that we can use
				for (int k : id[x])
					if (k < h)//Find deficit power.
						now -= (h - k); // sum, that we need
				now -= num0 * h; // sum, that we need
                            //-num0 *h accounts for deficit exponent for Ai where exponent of x is 0.
				if (now >= 0)
					l = h;
				else
					r = h;
			}
			for (int i = 0; i < l; i++) ans *= x;//multiply answer by x^l
		}

SOLUTION:

The solutions are also pasted in tab below for you guys to see. Please refer to them in case links dont work. @admin may need time to link solutions up :slight_smile:

Setter

Click to view
#include <bits/stdc++.h>

using namespace std;

const int maxl = (int)1e6 + 10;

int lp[maxl];
int cnt[maxl];
vector <int> d[maxl];

bool can(int n, int md, const vector <int> &d) {
    int need = md * (n - (int)d.size());
    for(int x: d) {
        if (x < md) need += md - x;
        else need -= (x - md) / 2;
    }
    return need <= 0;
}

int main() {
    lp[1] = 1;
    for(int i = 2; i < maxl; ++i) {
        if (lp* > 0) continue;
        for(int j = i; j < maxl; j += i) {
            if (lp[j] == 0) lp[j] = i;
        }
    }
    ios_base::sync_with_stdio(0);
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        memset(cnt, 0, sizeof cnt);
        for(int i = 1; i < maxl; ++i) {
            d*.clear();
        }
        for(int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            while(x > 1) {
                int p = lp[x];
                int c = 0;
                while(x > 1 && x % p == 0) x /= p, c++;
                d[p].push_back(c);
                cnt[p] += c;
            }
        }
        int gcd = 1;
        for(int p = 2; p < maxl; ++p) {
            if (cnt[p] < n) continue;
            int lf = -1, rg = 20;
            while(rg - lf > 1) {
                int md = (lf + rg) / 2;
                if (md == -1 || can(n, md, d[p])) {
                    lf = md;
                } else rg = md;
            }
            //lf now is the maximum power of p in gcd
            while(lf--) gcd *= p;
        }
        cout << gcd << '

';
}
return 0;
}

Tester

Click to view
#include <bits/stdc++.h>
#include <cassert>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
// read template
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
			
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			assert(cnt>0);
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
 
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
 
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
 
long long readIntLn(long long l,long long r){
	return readInt(l,r,'

');
}

string readStringLn(int l,int r){
	return readString(l,r,'

');
}

string readStringSp(int l,int r){
	return readString(l,r,' ');
}
// end
 
const int M = 1e5 + 239;
const int X = 1e6 + 239;
 
int n, a[M], mn[X];
vector<int> id[X];
vector<int> prime;
 
void solve()
{                        
	n = readIntLn(1, (int)(1e5));
	for (int i = 0; i < n; i++)
	{
		if (i < n - 1)
			a* = readIntSp(1, (int)(1e6));
		else
			a* = readIntLn(1, (int)(1e6));
	}
	for (int x : prime) id[x].clear();
	for (int i = 0; i < n; i++)
	{
		while (a* > 1)
		{
			int p = mn[a*];
			int k = 0;
			while (a* % p == 0)
			{
				a* /= p;
				k++;
			}
			id[p].push_back(k);
		}
	}
	int ans = 1;
	for (int x : prime)
		if (!id[x].empty()) // we can do operations for all primes independently, x - current prime
		{
			int l = 0;
			int r = 0;
			for (int k : id[x]) r = max(r, k + 1);
			int num0 = n - id[x].size();
			while (r - l > 1) // binary search for maximum possible power of x in answer
			{
				int h = (l + r) >> 1; // check x^h
				int now = 0;
				for (int k : id[x]) 
					if (k >= h)
						now += ((k - h) >> 1); // sum, that we can use
				for (int k : id[x])
					if (k < h)
						now -= (h - k); // sum, that we need
				now -= num0 * h; // sum, that we need
				if (now >= 0)
					l = h;
				else
					r = h;
			}
			for (int i = 0; i < l; i++) ans *= x;
		}
	cout << ans << "

";
}

int main()
{ 
	memset(mn, -1, sizeof(mn));
	for (int i = 2; i < X; i++)
		if (mn* == -1)
		{
			prime.push_back(i);          
			for (int j = i; j < X; j += i)
				if (mn[j] == -1)
					mn[j] = i;
		}
	int T = readIntLn(1, 5);
	while (T--) solve();		
	assert(getchar() == -1);	
	return 0;
} 

Time Complexity= O((K+N)logN) where K is number of primes in given constraints of A_i

CHEF VIJJU’S CORNER :smiley:

1. Is this problem solvable if we raise constraint of A_i to 1 \le A_i \le {10}^{9}?

2. Usually, many problems using GCD need knowledge of Mobius Function, Euler Totient functions etc. There is a very good blog describing them here

3. Linear Sieve deserves a mention here. :slight_smile:

4. Prove that you can get an AC by this approach-

Click to view

Another possible solution:

Let g be gcd of initial numbers. Make a* = a* / g. Now, New gcd = 1.

Now consider only primes until 100 to find the new solution. We will not be able to add any prime > 100 after the 2nd step. let d be a prime > 100 such that {d}^{2} is divisible by A*, then if we divide this A* by {d}^{2} then A* will no longer be divisible by d. Let the answer for A*/g be denoted by ans

Final solution: ans * g.

For above approach, solve the following-

  • This approach considers only first 100 prime number. Validate and comment on its correctness. “Proof by AC” not accepted.
  • Can this approach be extended to A_i \le {10}^{9}. Why/Why not?
  • What is the lower bound on number of primes to consider for making it useful for A_i <{10}^{9} and A_i <{10}^{18}?

Credits for this question to - @codebreaker123


#2

Difference between (Line 135) ( lli mid=l+(r-l)/2 and lli mid=l+(r-l+1)/2 ) deserves a mention in CHEF VIJJU’S CORNER.

https://www.codechef.com/viewsolution/19315183 (TLE);

https://www.codechef.com/viewsolution/19311716 (AC)


#3

I missed the trick for storing lowest prime divisor for non primes. Good one!


#4

i think the complexity should be k.N.logN, please correct if i am wrong.


#5

Can anyone help me with my solution?

Solution link is:

link text


#6

another possible solution:

  1. let g <- gcd of initial numbers

  2. make a* = a* / g. new gcd = 1.

  3. Now consider only primes until 100 to find the new solution. We will not be able to add any prime > 100 after the 2nd step. let d be a prime > 100 such that d^2 is divisible by A*, then if we divide this A* by d^2 then A* will no longer be divisible by d. let the answer for A*/g -> ans

final solution: ans * g.

This can be extended for A* <= 10^9 (by considering primes upto 1000).

let me know if I am wrong.


#7

The tester solution is showing runtime error in my IDE.


#8

I’m having difficulty in understanding the binary search part . Can you explain with some example.


#9

What am I doing wrong?? I had the same logic but its giving me wrong answer.

https://www.codechef.com/viewsolution/19321011


#10

Your solution is really too detailed,Thank you :slight_smile:


#11

Can you please explain with the help of an example?


#12

The proof to my solution:

Let g be the gcd of As.
Now the gcd of A
/g to will be 1. (Pretty straight forward to see. Consider gcd be x. If gcd > 1, it contradicts that gcd of A* is g as every A* will then be divisible by g*x)

Now consider any number d> 100. In the best case, d can divide (n-1) numbers and maximum power of d on any of the nimber is 2. So, consider that d^2 divides (n-1) numbers. Now we have 2 cases:

  1. Divide a number by d^2 and multiply the last number by d. The will make the last number divisible by d but the number which was divided by d^2 no longer divisible by d. Which brings us to the same position except now we have (n-2) numbers divisible by d^2 and 1 number divisible by only d and last number still not divisible by d.

  2. Divide the number by d^2 and multiply a number which was already divisible by d^2 by d. In this case, tgere are (n-1) numbers divisble by d^2, 1 by d^3 (lets say this a) and 2 numbers non divisble by d. If you try to divide a by d^2 then a will be divisible by d and multiply a number no divisble by d. It will brng us to the same case as above. (You can prove this by induction that this will also not work)

You can also see that the numbers cant be made divisible by d by using the tester can function for md=1. You need 1 more divisor, how ever you can get int((2-1)/2) * (n-1) divisors = 0.

I rest my case.


#13

for (int k : id[x])
if (k >= h)//Find excess power
now += ((k - h) >> 1); // sum, that we can use

 for (int k : id[x])
     if (k < h)//Find deficit power.
     now -= (h - k); // sum, that we need

Consider this part of the code, it has O(n) complexity in itself.
So the overall complexity should be O(k.n.lg(H)) per test case.
Correct me if I’m wrong anywhere.


#14

If anyone can tell me why code is giving me a run error it’ll be great :slight_smile:
https://www.codechef.com/viewsolution/19341290


#15

Very nice,detailed and easy to get editorial.Really loved it.


#16

help me… i am getting tle
solution link
code written in java


#17

Can it be done in this manner:

Calculate total number of times a prime number appears in the factorization of every array elements like in example 3,15,15,27,1024 total number of 3’s are six and 2’s are ten.
Now simply multiply all the prime numbers with count greater than or equal to number of elements+1.

Please tell me if I am wrong?


#18

https://www.codechef.com/viewsolution/20550090

Can some one help me understand, why is my solution giving wrong answer.


#19

problem links are pointing to different problem bro. Nice work btw


#20

Thanks for telling that. The time in hand to prepare editorials was lesser than a drop of sand xD