SEAGCD - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sergey Nagin
Tester 1: Minako Kojima
Tester 2: Shiplu Hawlader
Editorialist: Pawel Kacprzak

DIFFICULTY:

MEDIUM

PREREQUISITES:

Number theory

PROBLEM:

You are given 4 integers: N, M, L, R. Your task is to count the number of arrays consisting of N elements less or equal M, for which the greatest common divisor of all elements in one such array is a number in range [L, R]. Since this number can be quite big, calculate it modulo 10^9 + 7.

QUICK EXPLANATION:

At the first look the problem may look quite difficult, but actually it is not. The crucial thing here is to look at it a little out of box and define two tables:

Let A[d] be the number of arrays consisting of N elements less or equal M, for which the greatest common divisor of all elements is divisible by d.

Let B[d] be the number of arrays consisting of N elements less or equal M, for which the greatest common divisor of all elements is equal d.

I encourage you to come up with a solution based on these two definitions. If you want a more briefly description, please check the next section.

EXPLANATION:

For the definitions of A[d] and B[d] please check the previous section.

First observe that for a fixed d, A[d] equals (M / d)^N, because for every position in an array, you can choose any of M / d elements from range [1…d] (there are M / d elements divisible by d in that range).

Let’s assume, that you want to compute B[d] and you have already computed B[2 * d], B[3 * d], …, B[k * d], where k is a maximum number for which k * d <= M.

Let S := B[2 * d] + B[3 * d] + … + B[k * d]

In order to compute B[d], we just need to observe that B[d] = A[d] - S. It is very clear if you look again at the definitions of A[d] and B[d].

Based on the above fact, we can compute B[d] in a decreasing order of d, i.e. d = M, M - 1, M - 2, …, 1.

Using this method, you can write a really nice and compact solution (remember to calculate
the answer modulo 10^9 + 7):

In the following code, mypow(a, b) is a function which compute (a^b) mod (10^9 + 7) using fast exponentiation.

First snippet presents an idea in pseudo-code of an implementation while the second one represents my solution and it is fast enough to pass all testcases and it is written in C++. Pseudo-code omits calculating the result modulo 10^9 + 7 in order to achieve better readability.

Pseudo code:

answer = 0;
for(d = M; d >= 1; --d)
    A[d] = mypow(M / d, N);
    S = 0;
    k = 2 * d;
    while(k <= M)
        S += B[k];
        k += d;
    B[d] = A[d] - S;
    if(d >= L && d <= R) 
        answer += B[d];
print answer

C++ code:

You have to be aware of time limit here, so calculate modulo only if needed and do not compute A[d] for every d, because if M / d1 == M / d2, then A[d1] = A[d2].

int answer = 0;
int last = -1;
int power;
for(int d = M; d >= 1; --d)
{
    int div = M / d;
    if(div != last)
    {
        power = mypow(div, N);
        last = div;
    }
    A[d] = power;
    int S = 0;
    int k = 2 * d;
    while(k <= M)
    {
        S += B[k];
        if(S >= MOD) S %= MOD;
        k += d;
    }
    B[d] = A[d] - S;
    if(B[d] < 0) B[d] += MOD;
    if(B[d] >= MOD) B[d] %= MOD;
    if(d >= L && d <= R) 
    {
        answer += B[d];
        if(answer >= MOD) answer %= MOD;
    }
}
cout << answer << endl;

Time Complexity:

The time complexity here is O(M * log(M)) per one testcase, because we loop over M values in the main loop and the inside while-loop takse O(log(M)) time. Also computing A[d] takes O(M * log(M)) time.

AUTHOR’S AND TESTER’S SOLUTIONS:

To be uploaded soon.

RELATED PROBLEMS:

To be uploaded soon.

4 Likes

Somewhat similar to SRM 613 550-pointer Random GCD. Both of them are nice.

1 Like

I used this approach only.
[My code][1].

It was giving TLE in the last case.
Finally to reduce my time taken I changed some things.

  1. I prime factorized every number till the maximum M provided in all the test cases.
  2. As the power was raised by N for every number. I saved power of N for every prime.
  3. When I calculated the power of any number. I just multiplied power of each prime it consisted of(and how many powers of that prime it consisted of).

[2]

It also gave TLE. I figured that for 2,3,5,7 for storing primes it would require additional M/2,M/3,M/5,M/7 computations.
So, I started storing primes from 11 rather than 2 and when I calculated the power of a number. I first calculated the powers of 2,3,5,7 it has then used the prime factorization I pre-computed.

It was just under the time limit. [Final Code][3]. Time - 14.92 seconds.

I just managed to get it under the time limit. There might be another solution as I have seen people with much less time.

It would really be helpful if any other solution to this problem can be posted here.

  [1]: http://www.codechef.com/viewsolution/5549972
  [2]: http://www.codechef.com/viewsolution/5552506
  [3]: http://www.codechef.com/viewsolution/5560673
2 Likes

I applied the same approach mentioned in the editorial . But one thing to notice is that is if m/d1= m/d2 then B[d1] = B[d2] then we do not need to check when to calculate modulo…

Proof can be found by considering the lemmas mentioned by Lalit Kundu in this link http://www.quora.com/What-is-the-approach-to-solve-Hyperrectangle-GCD-problem-of-Codesprint5-URL-for-the-problem-HackerRank

my solution http://www.codechef.com/viewsolution/5598043

1 Like

Please Explain what are arrays A and B representing.

I think a better solution exists.
Got AC in 0.46 sec.

Just take a look at my solution.

http://www.codechef.com/viewsolution/5558373

4 Likes

I used the fact that the number of arrays of N elements between 1 and X with GCD equal to 1 is:

a(X, N) = sum(µ(k)*floor(X/k)^N, k=1…n) where µ is the Möbius function.

And the number of arrays of N elements between 1 and M with GCD equal to D is: a(floor(M/D), N)

The final answer is sum(a(floor(M/D), N), D=L…R)

By using the same approach as in SEPT14/FLOORI4, we can compute the first sum in O(log(N) sqrt(M)) which makes the complexity of the computation of the second sum: O(log(N) sqrt(M) sqrt(M))

And as we can precompute µ(k) for k between 1 and M in O(M log(M)), the total Complexity is O(M log(M) + M log(N))

Here is my solution: 5533797

2 Likes

Hello all i followed this approach
please review code from http://www.codechef.com/viewsolution/5569341

Algorithm:-
Fact:
1)‘r’ objects can be arranged in ‘n’ places with repetitions :Math.pow(r,n);
2)if d is the GCD of n numbers then all n(at least one ==d) numbers are divisible by d

I have applied above facts to solve this problem

For each test case
allFactors is list that can store all numbers divisible by all d’s

for all d(L to R)
	
	localFactors: is list that can store all numbers divisible by current 'd' 
	 

	1)store all numbers(<=M) divisible by d(including d)  in localFactors
	2)Get the size of localFactors 
	3)Now the Math.pow(size,n)%mod give all the GCD of numbers stored in 						localFactors
	4)Now localFactors contains numbers for those
		a)the GCD out of Range that is >R 
			a.1)this can be eliminated by finding how many(Rc) out of Range >R 
			a.2)subtract Math.pow(Rc,n)%mod from 3
		b) GCD alreader included in previous iteration
			for all numbers(dr) common to both  localFactors and  allFactors
			     b.1)get count(cd) of numbers(<=M) that can be divisible by 'dr' 
			      b.2)subtract Math.pow(cd,n) %modfrom 4)a.2
	5)clear all  localFactors.clear()	
end for

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;

public class Main {
public static int getFactorCnt(int num, int M) {
int count = 0;
count=(M-num)/num;
return count+1;
}

public static void main(String[] args) {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	try {
		int t = Integer.parseInt(br.readLine());
		String d[] = null;
		long mod = 1000000000 + 7;
		long result = 0;
		int N = 0, M = 0, L = 0, R = 0;
		HashSet<Integer> gcdGlobalFactor = new HashSet<Integer>();
		ArrayList<Integer> gcdoutOfRange = new ArrayList<Integer>();
		ArrayList<Integer> gcdlocalFactors = new ArrayList<Integer>();
		int fc = 0;
		long modCnt = 0;
		for (int i = 0; i < t; i++) {
			result = 0;
			d = br.readLine().split(" ");
			
			N = Integer.parseInt(d[0]);
			M = Integer.parseInt(d[1]);
			L = Integer.parseInt(d[2]);
			R = Integer.parseInt(d[3]);
			
			gcdGlobalFactor.clear();
			for (int D = L; D <= R; D++) {

				gcdoutOfRange.clear();
				
				gcdlocalFactors.clear();
				if(gcdGlobalFactor.contains(D)){
					continue;
				}
				
				for (int j = 2; j < M + 1; j++) {
					if (D * j <= M) {
						if(D*j>R){
							gcdoutOfRange.add(D*j);
						}
						if(gcdGlobalFactor.contains(D*j)&&(D*j<=R)){
							gcdoutOfRange.add(D*j);
						}
						gcdGlobalFactor.add(D * j);
						gcdlocalFactors.add(D*j);
					} else {
						break;
					}
				}
				
				int len = gcdlocalFactors.size();
				
				if (len == 0) {
					result +=1; 
					result = result % mod;
					continue;
				}
				
				modCnt = (long) Math.pow(len+1, N);
				result += modCnt;

				len=gcdoutOfRange.size();
				
				for (int j = 0; j < len; j++) { 
					fc = getFactorCnt(gcdoutOfRange.get(j), M);
					result = (long) (result - Math.pow(fc, N)); 
				}
				result = result % mod;
			}
			System.out.println(result);
		}
	} catch (NumberFormatException | IOException e) {
		// TODO Auto-generated catch block
		e.printStackTrace();
	}
}

}

Hello Martin Suska,please review
http://www.codechef.com/viewsolution/5569341
Regards
Samuel

I am unable to understand the question. will somebody explain with an example. What will the initial array contain? do we have arrays of arrays?

Can Anybody tell what’s wrong with this solution. I am getting WA for this
http://www.codechef.com/viewsolution/5793327

If some one look this it will be great hel[ to me
http://www.codechef.com/viewsolution/5569341
Regards
Samuel

please see the formated code from :
http://www.codechef.com/viewsolution/5569341

Hello all Please review my code
http://www.codechef.com/viewsolution/5569341
please let me know why it is not working
Regards
Samuel

I like this one, it was nice :wink:

Can you explain what you precompute in array A?

A* tells me total no. of possible ways in which n nos are selected from 1 to i so that GCD is 1.
Now as told A* = (tot of possible ways) - sum(gcd=2,3,…,i)

(GCD=2)=A[i/2] as explained,and so on.
what I do is I combine (GCD=i/3+1)to(GCD=i/2) in 1 slot as all of them is equal to A[2], (GCD=i/4+1)- (GCD=i/3) in 1 slot = A[3], and so on…, which are already computed.

Now for any m u can also see u only need 2*sqrt(m) values A[1], A[2], A[3],…A[sqrt(m)], A[m/sqrt(m)],…A[m/2],A[m/1].
This is because for all l<=k<=r u can calculate no of possible ways st gcd=k using array A.

4 Likes

Thank you :slight_smile:

Why you do not add link to your previous comment instead of bad formatted code?