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.
