GCDARR2. GCD Arrays (Hard)

Problem Statement

an array $A$ of length $N$ is called good if:

• $\gcd(A_1, A_2, \ldots, A_N) = 1$
• $\gcd(A_L, A_{L+1}, \ldots, A_R) \ne 1$ for every $(L, R) \ne (1, N)$

every proper subsegment (any contiguous subarray except the full array itself) must have gcd $> 1$, but the full array’s gcd must be exactly 1.

given $N$ and $M$, count the number of good arrays of length $N$ with $1 \le A_i \le M$. print the answer modulo $998244353$.

Examples

Example 1

5
3 3
3 6
3 12
4 12
200000 100

0
4
42
74
263141891

for $N=3$, $M=6$: the 4 valid arrays are $[2,6,3]$, $[3,6,2]$, $[4,6,3]$, $[3,6,4]$.

take $[2, 6, 3]$:

• $\gcd(2, 6, 3) = 1$ ✓ (full array)
• $\gcd(2, 6) = 2 \ne 1$ ✓
• $\gcd(6, 3) = 3 \ne 1$ ✓
• $\gcd(2) = 2 \ne 1$ ✓, $\gcd(6) = 6 \ne 1$ ✓, $\gcd(3) = 3 \ne 1$ ✓

for $N=3$, $M=3$: no valid arrays exist — we’ll see why during the explanation.

Constraints

• $1 \le T \le 50$
• $3 \le N \le 2 \cdot 10^5$
• $3 \le M \le 2 \cdot 10^5$
• sum of $M$ over all test cases $\le 2 \cdot 10^5$

Explanation

brute force

try all $M^N$ arrays. for each, check both gcd conditions. that’s $M^N \cdot N \log M$ — completely hopeless for the given constraints.

we need structure.

what does a valid array look like?

let’s say $N = 3$, so the array is $[A_1, A_2, A_3]$. the proper subsegments are: $[A_1]$, $[A_2]$, $[A_3]$, $[A_1, A_2]$, $[A_2, A_3]$. all of these must have gcd $> 1$.

• $[A_1]$ having gcd $> 1$ just means $A_1 > 1$.
• $[A_1, A_2]$ having gcd $> 1$ means $A_1$ and $A_2$ share a prime.
• $[A_2, A_3]$ having gcd $> 1$ means $A_2$ and $A_3$ share a prime.
• but $\gcd(A_1, A_2, A_3) = 1$ — they can’t all share the same prime.

for $N=3$, $M=3$: the interior is just $A_2 \in \{2, 3\}$ (can’t be 1). if $A_2 = 2$, then $A_1$ must share a factor with 2 so $A_1 \in \{2\}$, and $A_3 \in \{2\}$. but then $\gcd(2, 2, 2) = 2 \ne 1$. if $A_2 = 3$, same problem. so 0 valid arrays ✓.

the structure for general $N$

take any valid array. consider the interior elements $A_2, A_3, \ldots, A_{N-1}$. every subarray made only from interior elements is a proper subarray, so its gcd $> 1$. in particular, $\gcd(A_2, A_3, \ldots, A_{N-1}) > 1$ — the entire interior shares a common factor.

let $g = \gcd(A_2, A_3, \ldots, A_{N-1})$. we know $g \ge 2$.

now for the endpoints:

• the subarray $[A_1, A_2, \ldots, A_{N-1}]$ must have gcd $> 1$. that’s $\gcd(A_1, g) > 1$ — so $A_1$ shares at least one prime with $g$.
• the subarray $[A_2, A_3, \ldots, A_N]$ must have gcd $> 1$. that’s $\gcd(g, A_N) > 1$ — so $A_N$ shares at least one prime with $g$.
• the full array must have gcd $= 1$, which means $\gcd(A_1, g, A_N) = 1$ — no single prime divides all three.

so the answer is:

$\text{Answer} = \sum_{g=2}^{M}\ \underbrace{\text{dp}[g]}_{\text{interior seqs with gcd exactly } g}\ \cdot\ \underbrace{\text{pairs}(g)}_{\text{valid endpoint pairs for this } g}$

where:

• $g$ — the gcd of the interior elements $A_2, \ldots, A_{N-1}$, iterated from 2 to $M$
• $\text{dp}[g]$ — number of length-$(N-2)$ sequences in $[1,M]$ with gcd exactly $g$
• $\text{pairs}(g)$ — number of valid $(A_1, A_N)$ pairs for this fixed interior gcd $g$

computing dp[g] — the “exactly g” trick

$\text{dp}[g]$ = number of sequences of length $N-2$ using elements from $[1, M]$ whose gcd is exactly $g$.

first, let’s count sequences whose gcd is at least $g$ (i.e., every element is a multiple of $g$). there are $\lfloor M/g \rfloor$ multiples of $g$ in $[1, M]$, so:

$\text{(sequences with gcd divisible by } g) = \left\lfloor \frac{M}{g} \right\rfloor^{N-2}$

but this overcounts — it includes sequences with gcd $2g$, $3g$, etc. we subtract those out:

$\text{dp}[g] = \left\lfloor \frac{M}{g} \right\rfloor^{N-2} - \sum_{\substack{k \ge 2 \\ kg \le M}} \text{dp}[kg]$

where:

• $\text{dp}[g]$ — sequences of length $N-2$ in $[1,M]$ with gcd exactly $g$
• $\lfloor M/g \rfloor$ — count of multiples of $g$ in $[1, M]$ (interior elements must all be multiples of $g$)
• $N-2$ — the interior length (total array minus both endpoints)
• $k$ — runs over $2, 3, 4, \ldots$ so $kg$ covers all proper multiples of $g$ up to $M$
• $\text{dp}[kg]$ — already computed (since $kg > g$), sequences with gcd exactly $kg$

compute from $g = M$ down to $g = 1$ so every $\text{dp}[kg]$ is already ready. total work: $O(M \log M)$ by the harmonic series ($\frac{M}{1} + \frac{M}{2} + \cdots \approx M \ln M$).

small example — dp with $N=4$, $M=6$ (interior has $N-2 = 2$ elements)

$\text{dp}[6] = \left\lfloor \frac{6}{6} \right\rfloor^2 = 1^2 = 1$ $\text{dp}[5] = \left\lfloor \frac{6}{5} \right\rfloor^2 = 1^2 = 1$ $\text{dp}[4] = \left\lfloor \frac{6}{4} \right\rfloor^2 = 1^2 = 1$ $\text{dp}[3] = \left\lfloor \frac{6}{3} \right\rfloor^2 - \text{dp}[6] = 4 - 1 = 3$ $\text{dp}[2] = \left\lfloor \frac{6}{2} \right\rfloor^2 - \text{dp}[4] - \text{dp}[6] = 9 - 1 - 1 = 7$

for $\text{dp}[2] = 7$: the 9 pairs of interior elements using only multiples of 2 are $\{2,4,6\}^2$, minus the pair with gcd 4 (just $(4,4)$) and gcd 6 (just $(6,6)$) = 7. ✓

computing pairs(g) — the Möbius trick

we need: how many pairs $(A_1, A_N) \in [1,M]^2$ satisfy:

• $\gcd(A_1, g) > 1$
• $\gcd(A_N, g) > 1$
• $\gcd(A_1, A_N, g) = 1$

step 1 — how many integers in $[1, M]$ share a prime with $g$?

let’s count the complement first: integers coprime to $g$.

if $g = 30 = 2 \times 3 \times 5$ and $M = 20$, we want integers from 1 to 20 not divisible by 2, 3, or 5. by inclusion-exclusion:

$20 - \lfloor 20/2 \rfloor - \lfloor 20/3 \rfloor - \lfloor 20/5 \rfloor + \lfloor 20/6 \rfloor + \lfloor 20/10 \rfloor + \lfloor 20/15 \rfloor - \lfloor 20/30 \rfloor$ $= 20 - 10 - 6 - 4 + 3 + 2 + 1 - 0 = 6$

the Möbius function packages these alternating $\pm$ signs automatically:

$\mu(n) = \begin{cases} 1 & n = 1 \\ (-1)^k & n \text{ is a product of } k \text{ distinct primes} \\ 0 & n \text{ has a squared prime factor} \end{cases}$

for divisors of $30$:

so the inclusion-exclusion above is exactly:

$S_g = \sum_{d \mid g} \mu(d) \left\lfloor \frac{M}{d} \right\rfloor$

where:

• $S_g$ — count of integers in $[1, M]$ coprime to $g$
• $d \mid g$ — $d$ runs over every divisor of $g$
• $\mu(d)$ — Möbius value: $+1$ for even number of distinct prime factors, $-1$ for odd, $0$ if any squared prime factor (those cancel and are skipped)
• $\lfloor M/d \rfloor$ — count of multiples of $d$ in $[1, M]$

and it counts the integers in $[1, M]$ coprime to $g$. why does this work? the Möbius function has a key identity: for any $n > 1$,

$\sum_{d \mid n} \mu(d) = 0$

this cancellation is exactly what makes the inclusion-exclusion over prime subsets exact — overcounted elements cancel out.

so: $M - S_g$ integers share at least one prime with $g$. both endpoints need this, giving $(M - S_g)^2$ candidate pairs.

step 2 — subtract pairs where $\gcd(A_1, A_N, g) > 1$

a pair is invalid if some prime $p \mid g$ divides both $A_1$ and $A_N$. count these using the same inclusion-exclusion idea, but now for pairs:

$\text{pairs}(g) = (M - S_g)^2 + \sum_{\substack{d \mid g \\ d > 1}} \mu(d) \left\lfloor \frac{M}{d} \right\rfloor^2$

where:

• $\text{pairs}(g)$ — count of valid $(A_1, A_N)$ endpoint pairs for interior gcd $g$
• $(M - S_g)^2$ — both endpoints chosen from integers sharing a prime with $g$
• $d \mid g,\ d > 1$ — $d$ runs over non-trivial divisors of $g$ (skipping $d=1$)
• $\lfloor M/d \rfloor^2$ — pairs where both $A_1$ and $A_N$ are divisible by $d$
• $\mu(d)$ — inclusion-exclusion sign, same as before but now applied to pairs

$\lfloor M/d \rfloor^2$ vs $\lfloor M/d \rfloor$: if $\lfloor M/d \rfloor$ counts elements divisible by $d$, then $\lfloor M/d \rfloor^2$ counts pairs where both are — that’s the set being inclusion-excluded.

traced example — $g = 6$, $M = 6$

$S_6 = 1 \cdot 6 + (-1) \cdot 3 + (-1) \cdot 2 + 1 \cdot 1 = 6 - 3 - 2 + 1 = 2$ $\text{coprime to 6: } \{1, 5\} \quad ✓$

$M - S_6 = 4 \quad \text{(share a prime with 6: } \{2, 3, 4, 6\})$

base: $4^2 = 16$ candidate pairs.

correction ($d > 1$, both endpoints divisible by $d$):

• $d = 2$: $\mu(2) \cdot 9 = -9$ (pairs where both divisible by 2: $\{2,4,6\}^2 = 9$)
• $d = 3$: $\mu(3) \cdot 4 = -4$ (pairs where both divisible by 3: $\{3,6\}^2 = 4$)
• $d = 6$: $\mu(6) \cdot 1 = +1$ (pairs where both divisible by 6: $\{6\}^2 = 1$, added back)

correction total: $-9 - 4 + 1 = -12$.

$\text{pairs}(6) = 16 - 12 = 4 \quad ✓$

the 4 valid pairs are $(A_1, A_N) \in \{(2,3),(4,3),(3,2),(3,4)\}$ — $A_1$ is divisible by 2 only, $A_N$ by 3 only (or vice versa), so no shared prime with $g=6$ on both endpoints simultaneously.

putting it all together

for $N=3$, $M=6$: the only $g$ giving non-zero pairs is $g = 6$ (pairs = 4, dp[6] = 1). all other $g$ have pairs = 0 because the prime structure of small $g$ forces both endpoints to share the same factor, violating the gcd = 1 condition.

answer = $\sum_{g=2}^{6} \text{dp}[g] \cdot \text{pairs}(g) = 1 \cdot 4 = 4$ ✓.

complexity

since sum of $M \le 2 \cdot 10^5$, total across all test cases is fine.

Code

void solve() {
    long long N, M; cin >> N >> M;

    vector<long long> dp(M + 1, 0);
    for (long long g = M; g >= 1; g--) {
        dp[g] = pw(M / g, N - 2);
        for (long long k = 2 * g; k <= M; k += g)
            dp[g] = (dp[g] - dp[k] + MOD) % MOD;
    }

    long long ans = 0;
    for (long long g = 2; g <= M; g++) {
        if (!dp[g]) continue;

        // S_g = #{x in [1,M] : gcd(x,g) = 1}  via Möbius
        long long Sg = 0;
        for (int d : divs[g]) {
            if (!mu[d]) continue;
            long long fl = (M / d) % MOD;
            if (mu[d] == 1) Sg = (Sg + fl) % MOD;
            else            Sg = (Sg - fl + MOD) % MOD;
        }
        long long MSg = (M % MOD - Sg + MOD) % MOD;
        long long pairs = MSg * MSg % MOD;

        // inclusion-exclusion correction: sum_{d|g, d>1} mu(d)*floor(M/d)^2
        for (int d : divs[g]) {
            if (d == 1 || !mu[d]) continue;
            long long fl = (M / d) % MOD;
            long long term = fl * fl % MOD;
            if (mu[d] == 1) pairs = (pairs + term) % MOD;
            else            pairs = (pairs - term + MOD) % MOD;
        }
        ans = (ans + dp[g] * pairs) % MOD;
    }

    cout << ans << "\n";
}

Full code

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;
const int MAXM = 200001;

int mu[MAXM];
vector<int> divs[MAXM];

long long pw(long long a, long long b) {
    long long r = 1;
    a %= MOD;
    for (; b > 0; b >>= 1, a = a * a % MOD)
        if (b & 1) r = r * a % MOD;
    return r;
}

void precompute() {
    vector<int> primes;
    vector<bool> comp(MAXM, false);
    mu[1] = 1;
    for (int i = 2; i < MAXM; i++) {
        if (!comp[i]) { primes.push_back(i); mu[i] = -1; }
        for (int j = 0; j < (int)primes.size() && (long long)i * primes[j] < MAXM; j++) {
            comp[i * primes[j]] = true;
            if (i % primes[j] == 0) { mu[i * primes[j]] = 0; break; }
            mu[i * primes[j]] = -mu[i];
        }
    }
    for (int i = 1; i < MAXM; i++)
        for (int j = i; j < MAXM; j += i)
            divs[j].push_back(i);
}

void solve() {
    long long N, M; cin >> N >> M;

    vector<long long> dp(M + 1, 0);
    for (long long g = M; g >= 1; g--) {
        dp[g] = pw(M / g, N - 2);
        for (long long k = 2 * g; k <= M; k += g)
            dp[g] = (dp[g] - dp[k] + MOD) % MOD;
    }

    long long ans = 0;
    for (long long g = 2; g <= M; g++) {
        if (!dp[g]) continue;

        long long Sg = 0;
        for (int d : divs[g]) {
            if (!mu[d]) continue;
            long long fl = (M / d) % MOD;
            if (mu[d] == 1) Sg = (Sg + fl) % MOD;
            else            Sg = (Sg - fl + MOD) % MOD;
        }
        long long MSg = (M % MOD - Sg + MOD) % MOD;
        long long pairs = MSg * MSg % MOD;
        for (int d : divs[g]) {
            if (d == 1 || !mu[d]) continue;
            long long fl = (M / d) % MOD;
            long long term = fl * fl % MOD;
            if (mu[d] == 1) pairs = (pairs + term) % MOD;
            else            pairs = (pairs - term + MOD) % MOD;
        }

        ans = (ans + dp[g] * pairs) % MOD;
    }

    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    precompute();
    int T; cin >> T;
    while (T--) solve();
}

Complexity

• Preprocessing: $O(M \log M)$ — linear sieve + divisor lists
• Per test case: $O(M \log M + M \log N)$ — dp sweep + pairs computation
• Total: $O(M \log M + M \log N)$ summed over test cases (sum of $M \le 2 \cdot 10^5$)

Resources

• GCDARR2 — problem
• editorial
• GCDARR — easier version — same dp[g] formula, start here
• ABC162E — Sum of gcd of Tuples (Hard) — same exact-GCD DP, full array version
• CF 1750D — Count GCD — inclusion-exclusion over divisors
• COPRIME3 — Coprime Triples — Möbius for exact GCD, simpler warmup
• cp-algorithms — Inclusion-Exclusion
• Möbius Inversion for CP — harmonic series + floor-block trick