PROBLEM LINK:Author: Sergey Nagin 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 pseudocode 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++. Pseudocode 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 whileloop 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

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

Somewhat similar to SRM 613 550pointer Random GCD. Both of them are nice. answered 15 Dec '14, 23:34

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/WhatistheapproachtosolveHyperrectangleGCDproblemofCodesprint5URLfortheproblemHackerRank my solution http://www.codechef.com/viewsolution/5598043 answered 16 Dec '14, 08:28

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

Please Explain what are arrays A and B representing. answered 16 Dec '14, 09:07

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
answered 18 Dec '14, 17:49

Hello Martin Suska,please review http://www.codechef.com/viewsolution/5569341 Regards Samuel answered 19 Dec '14, 22:28

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

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

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

please see the formated code from : http://www.codechef.com/viewsolution/5569341 answered 07 Jan '15, 18:38

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

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=(Mnum)/num; return count+1; }
} answered 19 Dec '14, 13:56

I like this one, it was nice ;)
It was a good question ^_^