problem

次のような問題が$t \le 10^5$個与えられるのですべて解け:

正整数$A, B, C$が与えられる。 $P = \{ \, \{\{ a, b, c \}\} \mid a | A, \, b | B, \, c | C \}$ として $\#P$ を求めよ。 ただし $\{\{ x, y, z, \dots \}\}$ は多重集合。

solution

約数全体を$2^3$種に分類。組合せを総当たりし重複組合せ${}_nH_r$$で求める。$A, B, C$の最大値を$L$とし$d(n)$を約数の個数の上界として$O(L \log L + t d(L))$。

$a, b, c$として考慮する値は$A, B, C$の約数だけでよい。 約数の集合$D(n) = \{ x \mid x | n \}$をおき$D = D(A) \cup D(B) \cup D(C)$とする。 $D_{101} = \{ x \in D \mid x \in D(A), \, x \not\in D(B), \, x \in D(C) \}$などとして$D$を$2^3$個の互いに素な集合に分割する。 元$d \in D$がどこに分類されたかを表す関数を$k : D \to 2^3$とする。 多重集合 $\{\{ x, y, z \}\} \in P$ に対しそれらがどこから来たかの多重集合 $K(x, y, z) = \{\{ k(x), k(y), k(z) \}\}$ を考える。 ある $K(x, y, z)$ の値を持つような多重集合の個数は整数$\#D_{k(x)}, \#D_{k(y)}, \#D_{k(z)}$から重複組合せを使って求めらる。 これを高々${}_{2^3}C_3$通りすべて見て足し合わせれば答えとなる。 ただしここで$x \le y \le z$という制約を入れてさらに分割してしまうと、集合$D_{k(x)}, D_{k(y)}, D_{k(z)}$の中を覗かなければいけなくなってしまうことに注意する。

note

$x \le y \le z$まで細かくしてしまうと失敗するの不思議。これのせいで解けなかった

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;
template <typename T> ostream & operator << (ostream & out, vector<T> const & xs) { REP (i, int(xs.size()) - 1) out << xs[i] << ' '; if (not xs.empty()) out << xs.back(); return out; }

ll powmod(ll x, ll y, ll m) {
    assert (0 <= x and x < m);
    assert (0 <= y);
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z = z * x % m;
        x = x * x % m;
    }
    return z;
}
ll modinv(ll x, ll p) {
    assert (x % p != 0);
    return powmod(x, p - 2, p);
}

template <int32_t MOD>
int32_t fact(int n) {
    static vector<int32_t> memo(1, 1);
    while (n >= memo.size()) {
        memo.push_back(memo.back() *(int64_t) memo.size() % MOD);
    }
    return memo[n];
}
template <int32_t PRIME>
int32_t inv_fact(int n) {
    static vector<int32_t> memo(1, 1);
    while (n >= memo.size()) {
        memo.push_back(memo.back() *(int64_t) modinv(memo.size(), PRIME) % PRIME);
    }
    return memo[n];
}

template <int MOD>
int choose(int n, int r) {
    assert (0 <= r and r <= n);
    return fact<MOD>(n) *(ll) inv_fact<MOD>(n - r) % MOD *(ll) inv_fact<MOD>(r) % MOD;
}
template <int MOD>
int multichoose(int n, int r) {
    if (n == 0 and r == 0) return 1;
    return choose<MOD>(n+r-1, r);
}

void split_to_disjoint(const vector<int> & a, const vector<int> & b, const vector<int> & c, array<vector<int>, 8> & d) {
    int i = 0, j = 0, k = 0;
    while (a[i] != INT_MAX or b[j] != INT_MAX or c[k] != INT_MAX) {
        int x = min({ a[i], b[j], c[k] });
        int mask = (x == a[i] ? 1 : 0) | (x == b[j] ? 2 : 0) | (x == c[k] ? 4 : 0);
        d[mask].push_back(x);
        if (x == a[i]) ++ i;
        if (x == b[j]) ++ j;
        if (x == c[k]) ++ k;
    }
}

ll count_increasing(int i, int j, int k, const array<vector<int>, 8> & d) {
    constexpr int MOD = 1000000007;
    int a = d[i].size();
    int b = d[j].size();
    int c = d[k].size();
    if (not a or not b or not c) return 0;
    if (i == j and j == k) {
        return multichoose<MOD>(a, 3);
    } else if (i == j) {
        return multichoose<MOD>(a, 2) * c;
    } else if (j == k) {
        return multichoose<MOD>(b, 2) * a;
    } else if (k == i) {
        return multichoose<MOD>(c, 2) * b;
    } else {
        return a * b * c;
    }
}

int main() {
    // prepare a list of factors
    constexpr int LIMIT = 100000;
    vector<vector<int> > factors(LIMIT + 1);
    REP3 (x, 1, LIMIT + 1) {
        for (int kx = x; kx <= LIMIT; kx += x) {
            factors[kx].push_back(x);
        }
    }
    REP (x, LIMIT + 1) {
        factors[x].push_back(INT_MAX);  // as sentinels
    }

    // prepare the list of combinations
    vector<array<int, 3> > ps;
    for (int i : { 0x1, 0x3, 0x5, 0x7 }) {
        for (int j : { 0x2, 0x3, 0x6, 0x7 }) {
            for (int k : { 0x4, 0x5, 0x6, 0x7 }) {
                array<int, 3> p = {{ i, j, k }};
                sort(ALL(p));
                ps.push_back(p);
            }
        }
    }
    sort(ALL(ps));
    ps.erase(unique(ALL(ps)), ps.end());

    // input
    int t; scanf("%d", &t);
    vector<int> a(t), b(t), c(t);
    REP (i, t) {
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
    }

    // solve
    vector<ll> cnt(t);
    REP (i, t) {
        array<vector<int>, 8> d;
        split_to_disjoint(factors[a[i]], factors[b[i]], factors[c[i]], d);
        for (auto p : ps) {
            cnt[i] += count_increasing(p[0], p[1], p[2], d);
        }
    }

    // output
    REP (i, t) {
        printf("%lld\n", cnt[i]);
    }
    return 0;
}