SEAGCD - Editorial

dec14
editorial
medium
number-theory

#1

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.


#2

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


#3

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

#4

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


#5

Please Explain what are arrays A and B representing.


#6

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


#7

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


#8

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

#9

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();
	}
}

}


#10

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


#11

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?


#12

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


#13

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


#14

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


#15

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


#16

I like this one, it was nice :wink:


#17

Can you explain what you precompute in array A?


#18

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.


#19

Thank you :slight_smile:


#20

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