You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

This question is marked "community wiki".

asked 15 Dec '14, 22:50

pkacprzak's gravatar image

5★pkacprzak ♦♦
74485097
accept rate: 12%

I like this one, it was nice ;-)

(15 Dec '14, 23:30) betlista ♦♦3★

It was a good question ^_^

(20 Jan '15, 16:00) abcdexter242★

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

link

answered 16 Dec '14, 16:26

tapasjain01's gravatar image

6★tapasjain01
1063
accept rate: 0%

edited 27 Dec '14, 15:14

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) tapasjain016★

Thank you :)

(17 Dec '14, 07:33) mogers5★

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.

  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).

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.

link

answered 15 Dec '14, 23:42

pankaj_gudlani's gravatar image

4★pankaj_gudlani
212
accept rate: 0%

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

link

answered 15 Dec '14, 23:34

azukun's gravatar image

6★azukun
512
accept rate: 0%

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

link

answered 16 Dec '14, 08:28

hatim009's gravatar image

3★hatim009
46421122
accept rate: 8%

edited 16 Dec '14, 08:29

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

link

answered 17 Dec '14, 00:19

khalid545's gravatar image

4★khalid545
1163
accept rate: 12%

edited 17 Dec '14, 19:21

Please Explain what are arrays A and B representing.

link

answered 16 Dec '14, 09:07

aadil_ahmad's gravatar image

4★aadil_ahmad
296
accept rate: 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
link

answered 18 Dec '14, 17:49

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 0%

edited 20 Jan '15, 15:17

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

link

answered 19 Dec '14, 22:28

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 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?

link

answered 06 Jan '15, 13:13

codehalwai's gravatar image

1★codehalwai
11
accept rate: 0%

edited 06 Jan '15, 13:16

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

link

answered 07 Jan '15, 10:49

codehalwai's gravatar image

1★codehalwai
11
accept rate: 0%

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

link

answered 07 Jan '15, 18:35

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 0%

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

link

answered 07 Jan '15, 18:38

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 0%

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

link

answered 11 Jan '15, 11:31

jawa2code's gravatar image

3★jawa2code
24127
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<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();
    }
}

}

link

answered 19 Dec '14, 13:56

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 0%

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

(19 Dec '14, 14:32) betlista ♦♦3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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