D. Pave the Parallelepiped | Codeforces Round #497 (Div. 2)

とりあえず最大の入力以下の自然数の約数を列挙しておく。入力中最大の自然数をMとして、M以下の各自然数について、その倍数を見ていく。調和数を考えるとの計算量とわかる。

各データセットについて、別々に処理する。 A, B, Cのうち、少なくともひとつの約数になっている自然数の集合をSとする。これは事前に列挙した約数から簡単に求まる。Sの要素xについて、f(x)を xがA,B,Cのうちどれの約数になっているかのフラグとする。f(x)の値を数える。(のような感じで)3個の整数の選び方を考える。それぞれ順番を区別しないで数えるので注意。3値の大小は考慮せずに、{f(a),f(b),f(c)}=｛p,q,r}とする。(多重集合。p<=q<=r)。p,q,rを総当たりで固定する。p,q,rがすべて異なるとき、を数える。p=qかつq≠rのとき、フラグがp=qとなる自然数から2個、rとなる自然数から1個選ぶので、だけ数える。p≠qかつq=rの場合も同様。p=q=rのとき、を数える。なお、p,q,rがA,B,Cのすべての約数をカバーする必要があるので注意。そのためには、フラグp,q,rとA,B,Cの対応をすべて試せばよい。

vector<vector<int>> divisorsAll(int n) {
    vector<vector<int>> res(n + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; j += i) {
            res[j].push_back(i);
        }
    }
    return res;
}

int two(int n) {
    return n*(n + 1) / 2;
}
int three(int n) {
    return n*(n + 1)*(n + 2) / 6;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    int T;
    cin >> T;

    auto D = divisorsAll(100005);
    vi E(100005);
    each(d, D)sort(all(d));

    int di[200 * 3] = {};
    int A[3];
    rep(i, 3)A[i] = i;

    while (T--) {
        int S[3];
        int m = 0;

        vi X(8), Y(8);
        rep(i, 3) {
            cin >> S[i];
            int a = S[i];
            each(d, D[a]) {
                E[d] |= 1 << i;
                di[m++] = d;
            }
        }
        sort(di, di + m);
        m = unique(di, di + m) - di;
        
        rep(i, m)Y[E[di[i]]]++;
        int re = 0;

        rep(i, 8)FOR(j, i + 1, 8) {
            // {1,2}, {2,1}
            // i, j, j
            int ok = 0;
            do {
                if ((i >> A[0] & 1) && (i >> A[1] & 1) && (j >> A[2] & 1))ok |= 1;
                if ((i >> A[0] & 1) && (j >> A[1] & 1) && (j >> A[2] & 1))ok |= 2;
            } while (next_permutation(A, A + 3));
            if (ok & 1)re += two(Y[i]) * Y[j];
            if (ok & 2)re += Y[i] * two(Y[j]);
            FOR(k, j + 1, 8) {
                // {1, 1, 1}
                ok = 0;
                do {
                    if ((i >> A[0] & 1) && (j >> A[1] & 1) && (k >> A[2] & 1))ok |= 1;
                } while (next_permutation(A, A + 3));
                if (ok)re += Y[i] * Y[j] * Y[k];
            }
        }
        // {3}
        re += three(Y[7]);
        cout << re << endl;
        rep(i, m)E[di[i]] = 0;
    }
}