GCDARR - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Dynamic programming

PROBLEM:

Given N and M, count the number of integer arrays A of length N with elements in [1, M] such that:

  • \gcd(A_1, \ldots, A_N) = 1, and
  • \gcd(A_L, \ldots, A_R) \gt 1 for any (L, R) \ne (1, N)

In this version, N \le 2\cdot 10^5 and M \le 100.

EXPLANATION:

We want every subarray other than the full array to have a gcd that’s not 1.
In particular, note that this applies to the subarrays A[1, N-1] and A[2, N], each of which are length N-1.

Further, if these two subarrays have \gcd \gt 1, then every smaller subarray will automatically have \gcd \gt 1 as well!
This is because any smaller subarray can be formed by deleting some elements from one of these length-(N-1) subarrays; and deleting elements cannot reduce the gcd (in fact, the gcd will remain a multiple of the original.)

Thus, an array A being valid is equivalent to ensuring these three conditions:

  • \gcd(A_1, \ldots, A_{N-1}) \gt 1
  • \gcd(A_2, \ldots, A_{N}) \gt 1
  • \gcd(A_1, \ldots, A_{N})=1

Now, let’s deal with the first two conditions to begin with, i.e. the length-(N-1) subarrays having gcd larger than 1.
Note that these two subarrays share the common elements A_2, A_3, \ldots, A_{N-1} - they only differ in the endpoints where one of them includes A_1 while the other includes A_N.

So, we can split the array into three parts: [A_1], [A_2 \ldots A_{N-1}], and [A_N].

We know that the middle part must have a gcd that’s \gt 1 since it’s not the full array.
Let g = \gcd(A_2, \ldots, A_{N-1}).
Then, observe that we only need to ensure:

  • \gcd(A_1, g) \gt 1
    • This will give us \gcd(A_1, \ldots, A_{N-1}) \gt 1.
  • \gcd(A_N, g) \gt 1
    • This will give us \gcd(A_2, \ldots, A_{N}) \gt 1.
  • \gcd(A_1, A_N, g) = 1.
    • This will give us \gcd(A_1, \ldots, A_{N}) = 1.

In particular, once g is fixed we don’t care about the elements A_2, \ldots, A_{N-1} anymore: just that their gcd must be equal to g.

We use this observation to formulate a solution.

Let dp[g] denote the number of ways of choosing N-2 elements from the range [1, M] such that their gcd equals g.

dp[g] can be computed as follows.
We need to choose N-2 elements, and each of them certainly must be a multiple of g.

  • There are \left\lfloor \frac{M}{g} \right\rfloor multiples of g in the range [1, M].
  • So, if we let c_g = \left\lfloor \frac{M}{g} \right\rfloor, then there are (c_g)^{N-2} ways to just choose N-2 multiples of g.

However, not all of these choices are valid - some of them might have gcd’s that are larger than g.
Luckily, we know for sure that no matter what, the gcd will be a multiple of g.
This allows us to subtract out invalid choices - which are given by the dp definition!

Specifically, there are dp[k\cdot g] arrays whose gcd equals k\cdot g, for each k \ge 2.
So, we can just subtract out the values dp[2g], dp[3g], \ldots from the initial count, and hence end up with the final value of dp[g].

That is, we have

dp[g] = (c_g) ^ {N-2} - \sum_{k\ge 2} dp[k\cdot g]

Simply iterating through all values of k gives us a complexity of \mathcal{O}(M) per g, for \mathcal{O}(M^2) overall (it’s technically faster but we’ll come to that in the hard version - for now this analysis is enough.)

Once all the dp[g] values are known, we can use them to compute the answer.
Note that M \le 100 is quite small, allowing for the following algorithm:

  1. Fix the value of g = \gcd(A_2, \ldots, A_{N-2}).
    There are dp[g] ways to choose these elements, once g is fixed.
  2. Then, try all values of A_1 and A_N, each in the range [1, M].
    For each one, check if all three \gcd conditions are satisfied (on \gcd(g, A_1), \gcd(g, A_N), and \gcd(g, A_1, A_N).)
  3. If all three conditions are satisfied for some triple (g, A_1, A_N), add dp[g] to the answer.

This runs in \mathcal{O}(M^3 \log M) per test because there are \mathcal{O}(M^3) \gcd calls.
Still, with M \le 100 and at most 50 tests, this is more than fast enough.
It is possible to optimize out the log factor by precomputing gcds if you really want to.

TIME COMPLEXITY:

\mathcal{O}(M^3 \log M + M\log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
import math
mod = 998244353

for _ in range(int(input())):
    n, m = map(int, input().split())
    
    dp = [0]*(m+1)
    for x in reversed(range(1, m+1)):
        dp[x] = pow(m//x, n-2, mod)
        for y in range(2*x, m+1, x):
            dp[x] -= dp[y]
        dp[x] %= mod
        
    ans = 0
    for x in range(1, m+1):
        for y in range(1, m+1):
            for z in range(1, m+1):
                if math.gcd(x, y) > 1 and math.gcd(x, z) > 1 and math.gcd(x, y, z) == 1:
                    ans += dp[x]
    print(ans % mod)
GCDARR2 - Editorial