Nasser's GCD Triples#13084

Nasser's GCD Triples (Анализа на решението)

Solution

General Idea: We need to count, for each query, the triples $(i, j, k)$ (i, j, k) whose gcd lies in $[l, r]$ [l, r]. The key is to compute, for every value $g$ , the number of triples whose gcd is exactly $g$ , and then answer queries with prefix sums.

Let $c n t [x]$ be the number of elements equal to $x$ . Since $a_{i} \leq n$ a_i \le n, every gcd is also at most $n$ .

For each $g$ , let $s u m_{g}$ sum_g be the number of elements divisible by $g$ :

s u m_{g} = m : g ∣ m \sum c n t [m]

sum_g = \sum_{m \,:\, g \mid m} cnt[m]

Every triple chosen from these elements has a gcd that is a multiple of $g$ . So the number of triples whose gcd is a multiple of $g$ is:

f (g) = (3 s u m _{g})

f(g) = \binom{sum_g}{3}

Let $e x a c t (g)$ exact(g) be the number of triples whose gcd is exactly $g$ . Then $f (g)$ counts $e x a c t (g)$ exact(g) plus the triples whose gcd is a larger multiple of $g$ :

e x a c t (g) = f (g) - m = 2 g, 3 g, \dots \sum e x a c t (m)

exact(g) = f(g) - \sum_{m = 2g,\, 3g,\, \ldots} exact(m)

We compute this for $g$ from $n$ down to $1$ , so all larger multiples are already known when we reach $g$ .

After that, we build prefix sums over $e x a c t$ , so a query $(l, r)$ (l, r) is answered in $O (1)$ by:

p r e f [r] - p r e f [l - 1] (mod 1 0^{9} + 7)

pref[r] - pref[l-1] \pmod{10^9 + 7}

The binomial coefficients are computed with precomputed factorials and inverse factorials modulo $1 0^{9} + 7$ 10^9 + 7.

Computing $s u m_{g}$ sum_g and the inclusion-exclusion step both iterate over the multiples of each $g$ , which is a harmonic sum. So the solution runs in $O (n lo g n + q)$ \mathcal{O}(n \log n + q) per test case, after the one-time factorial precomputation.

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7, N = 1e6 + 5;
long long fact[N], invFact[N];
long long power(long long x, long long y, long long p) {
    long long res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1) res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
void precompute() {
    fact[0] = 1;
    for (long long i = 1; i < N; i++) fact[i] = (fact[i - 1] * i) % mod;
    invFact[N - 1] = power(fact[N - 1], mod - 2, mod);
    for (long long i = N - 2; i >= 0; i--)
        invFact[i] = (invFact[i + 1] * (i + 1)) % mod;
}
long long nCr(long long n, long long r) {
    if (r > n || n < 0 || r < 0) return 0;
    return ((fact[n] * invFact[r]) % mod * invFact[n - r]) % mod;
}
void solve() {
    int n, q;
    cin >> n >> q;
    vector<long long> gd(n + 1, 0), cnt(n + 1, 0);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        for (int j = i; j <= n; j += i) {
            sum += cnt[j];
        }
        gd[i] = nCr(sum, 3);
    }
    for (int i = n; i >= 1; i--) {
        for (int j = 2 * i; j <= n; j += i) {
            gd[i] -= gd[j];
            if (gd[i] < 0) gd[i] += mod;
        }
    }
    for (int i = 1; i <= n; i++) {
        gd[i] = (gd[i] + gd[i - 1]) % mod;
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        long long ans = gd[r] - gd[l - 1];
        if (ans < 0) ans += mod;
        cout << ans % mod << '\n';
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    precompute();
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}