### PROBLEM LINK:

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