×

# SEAGCD - Editorial

Author: Sergey Nagin
Tester 1: Minako Kojima
Editorialist: Pawel Kacprzak

MEDIUM

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)


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



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.

# RELATED PROBLEMS:

This question is marked "community wiki".

74485097
accept rate: 12%

I like this one, it was nice ;-)

(15 Dec '14, 23:30)

It was a good question ^_^

(20 Jan '15, 16:00)

 4 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 answered 16 Dec '14, 16:26 106●3 accept rate: 0% Can you explain what you precompute in array A? (16 Dec '14, 23:06) mogers5★ 4 A[i] 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[i] = (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. (17 Dec '14, 01:02) Thank you :) (17 Dec '14, 07:33) mogers5★
 2 I used this approach only. My code. It was giving TLE in the last case. Finally to reduce my time taken I changed some things. I prime factorized every number till the maximum M provided in all the test cases. As the power was raised by N for every number. I saved power of N for every prime. 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). Code 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. 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. answered 15 Dec '14, 23:42 21●2 accept rate: 0%
 1 Somewhat similar to SRM 613 550-pointer Random GCD. Both of them are nice. answered 15 Dec '14, 23:34 6★azukun 51●2 accept rate: 0%
 1 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 answered 16 Dec '14, 08:28 3★hatim009 464●2●11●22 accept rate: 8%
 1 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 answered 17 Dec '14, 00:19 116●3 accept rate: 12%
 0 Please Explain what are arrays A and B representing. answered 16 Dec '14, 09:07 29●6 accept rate: 0%
 0 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  answered 18 Dec '14, 17:49 24●1●2●7 accept rate: 0%
 0 Hello Martin Suska,please review http://www.codechef.com/viewsolution/5569341 Regards Samuel answered 19 Dec '14, 22:28 24●1●2●7 accept rate: 0%
 0 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? answered 06 Jan '15, 13:13 1●1 accept rate: 0%
 0 Can Anybody tell what's wrong with this solution. I am getting WA for this http://www.codechef.com/viewsolution/5793327 answered 07 Jan '15, 10:49 1●1 accept rate: 0%
 0 If some one look this it will be great hel[ to me http://www.codechef.com/viewsolution/5569341 Regards Samuel answered 07 Jan '15, 18:35 24●1●2●7 accept rate: 0%
 0 please see the formated code from : http://www.codechef.com/viewsolution/5569341 answered 07 Jan '15, 18:38 24●1●2●7 accept rate: 0%
 0 Hello all Please review my code http://www.codechef.com/viewsolution/5569341 please let me know why it is not working Regards Samuel answered 11 Jan '15, 11:31 24●1●2●7 accept rate: 0%
 -1 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 gcdGlobalFactor = new HashSet(); ArrayList gcdoutOfRange = new ArrayList(); ArrayList gcdlocalFactors = new ArrayList(); 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(); } }  } answered 19 Dec '14, 13:56 24●1●2●7 accept rate: 0% Why you do not add link to your previous comment instead of bad formatted code? (19 Dec '14, 14:32)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,683
×2,596
×631
×228

question asked: 15 Dec '14, 22:50

question was seen: 8,425 times

last updated: 20 Jan '15, 16:00