Codeforces Round #497 (Div. 1): B. Pave the Parallelepiped
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;
}