CF 1008D Pave the Parallelepiped

传送门

题目大意

给你一个 A×B×C A × B × C $A \times B \times C$ 的长方体，你要把它切成很多块大小都是 a×b×c a × b × c $a \times b \times c$ 的小长方体，要求只能沿 x x $x$ 轴等距切，沿 y$y$$y$ 轴等距切，沿 z z $z$ 轴等距切。问所有切的方案中能够切出多少种不同的小长方体。规定 a≤b≤c$a\le b\le c$$a \le b \le c$，也就是说 1×2×1 1 × 2 × 1 $1 \times 2 \times 1$ 的小长方体和 1×1×2 1 × 1 × 2 $1 \times 1 \times 2$ 的小长方体算一种小长方体。

有 t t $t$ 组询问。t≤105$t\le {10}^5$$t \le 10^5$； 1≤A,B,C≤105 1 ≤ A , B , C ≤ 10 5 $1 \le A, B, C \le 10^5$。

样例输入

4
1 1 1
1 6 1
2 2 2
100 100 100

样例输出

1
4
4
165

样例解释

对于第二组询问，有以下四种方案： 1×1×1 1 × 1 × 1 $1 \times 1 \times 1$， 1×1×2 1 × 1 × 2 $1 \times 1 \times 2$， 1×1×3 1 × 1 × 3 $1 \times 1 \times 3$， 1×1×6 1 × 1 × 6 $1 \times 1 \times 6$。

思路

首先用 O(nn−−√) O ( n n ) $O(n \sqrt n)$ 的时间复杂度预处理出所有数的因数。由于 105 10 5 $10^5$ 以内的数的因数个数最多只有 128 128 $128$ 个，因此不用担心空间不够。

一个很 Naive 的想法是，直接把三个数的因数个数乘起来，再来考虑算重的问题。看上去直接乘起来算重的情况是这样的：三个数都不同的情况算了 6 6 $6$ 次；有两个数相同的情况算了 3$3$$3$ 次；三个数都相同的情况算了 1 1 $1$ 次。发现三个数都相同的情况的方案数很好算，就是三个数都有的因数个数。我们继续考虑如何计算有两个数相同的情况。我们把这三个数的所有因数拿出来。对于只出现了两次的因数，第三个数显然可以取没有出现过的那个数的所有因数；对于出现了三次的因数，我们令前两个因数相同，那么第三个因数可以在所有因数中任取（除了前两个因数）。我们可以在 O(σ0)$O({\sigma }_0)$$O(\sigma_0)$ 的时间复杂度内计算出答案。

但是这样并不对，因为当三个数不同时，算重的情况是这样的：（举个例子，）对于一个三元组 (x,y,z)(x≤y≤z) ( x , y , z ) ( x ≤ y ≤ z ) $(x, y, z) \pod {x \le y \le z}$，它能够被 (A,B,C) ( A , B , C ) $(A, B, C)$ 切出来（换句话说， x∣A x ∣ A $x \mid A$ 且 y∣B y ∣ B $y \mid B$ 且 z∣C z ∣ C $z \mid C$），也能被 (A,C,B) ( A , C , B ) $(A, C, B)$ 切出来，但是不能被 (B,A,C) ( B , A , C ) $(B, A, C)$ 切出来。这种情况对于不同的三元组被算重的次数也是不同的，并不是固定的 6 6 $6$ 次，因此很难下手。

我们假设 (x,y,z)$(x,y,z)$$(x, y, z)$ 无需满足 x≤y≤z x ≤ y ≤ z $x \le y \le z$，然后再去统计满足 x∣A x ∣ A $x \mid A$， y∣B y ∣ B $y \mid B$， z∣C z ∣ C $z \mid C$ 的答案。那么对于一个合法的 (a,b,c)(a<b<c) ( a , b , c ) ( a < b < c ) $(a, b, c) \pod {a < b < c}$，它就真的被算了 6 6 $6$ 次了，其它情况同理。

由于现在 x$x$$x$ y y $y$z$z$$z$ 相互独立了，那么我们要求的东西实际上是：

$$(x, y, z) \mid (A, B, C) \text{ 或 } (x, y, z) \mid (A, C, B) \text { 或 } \cdots \text{ 或 } (x, y, z) \mid (C, B, A) \pod {x \le y \le z}$$
考虑容斥，那么我们现在首先要解决的问题是对于一个 (A,B,C) ( A , B , C ) $(A, B, C)$ 如何计算 (x,y,z) ( x , y , z ) $(x, y, z)$ 的个数。答案显然是它们 σ0 σ 0 $\sigma_0$ 的乘积。

考虑如何计算 (A,B,C)∧(A,C,B) ( A , B , C ) ∧ ( A , C , B ) $(A, B, C) \wedge (A, C, B)$ 的方案数。这相当于是要求 (A,gcd(B,C),gcd(B,C)) ( A , gcd ( B , C ) , gcd ( B , C ) ) $(A, \gcd(B, C), \gcd(B, C))$ 的方案数，还是这么做就可以了。

现在我们得到了 (x,y,z) ( x , y , z ) $(x, y, z)$ 不受顺序限制的方案数。对于三者都不同的情况，我们计算了 6 6 $6$ 次；对于有两者相同的情况，我们计算了 3$3$$3$ 次；对于三者相同的情况，我们计算了 1 1 <script type="math/tex" id="MathJax-Element-50">1</script> 次。前面已经说了计算两者相同和相同的计算方法，就这么做完了。

参考代码

注意快速排序是过不了的，必须写归并排序。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
using LL = long long;
using ULL = unsigned long long;
using std::cin;
using std::cout;
using std::endl;
using INT_PUT = int;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
    putchar('\n');
}

const int maxn = int(1e5);
std::vector<std::vector<int>> vec(maxn + 1);
void init()
{
    vec[1].push_back(1);
    for (int i = 2; i <= maxn; i++)
    {
        auto& v = vec[i];
        for (int j = 1; j * j <= i; j++)
        {
            if (!(i % j))
            {
                v.push_back(j);
                v.push_back(i / j);
            }
        }
        std::sort(v.begin(), v.end());
        v.resize(std::unique(v.begin(), v.end()) - v.begin());
    }
}
int Gcd(int a, int b)
{
    return !b ? a : Gcd(b, a % b);
}
int a[6][3];

int ans;
struct Node
{
    int val;
    int type;
    Node() {}
    Node(int val, int type) : val(val), type(type) {}
    bool operator<(const Node& b) const
    {
        if (val != b.val) return val < b.val;
        return type < b.type;
    }
    bool operator==(const Node& b) const
    {
        return val == b.val;
    }
};
std::vector<Node> all;
int CountAll()
{
    auto t = all;
    return std::unique(t.begin(), t.end()) - t.begin();
}

struct Triple
{
    int a, b, c;
    bool operator<(const Triple& y) const
    {
        if (a != y.a) return a < y.a;
        if (b != y.b) return b < y.b;
        return c < y.c;
    }
    Triple() {}
    Triple(int a, int b, int c) : a(a), b(b), c(c) {}
};
std::map<Triple, int> map;

void run()
{
    init();

    int T = readIn();
    while (T--)
    {
        for (int i = 0; i < 3; i++)
            a[0][i] = readIn();
        std::sort(a[0], a[0] + 3);
        auto triple = Triple(a[0][0], a[0][1], a[0][2]);
        if (map.count(triple))
        {
            printOut(map[triple]);
            continue;
        }
        int idx[3] = { 0, 1, 2 };
        for (int i = 1; i < 6; i++)
        {
            std::next_permutation(idx, idx + 3);
            for (int j = 0; j < 3; j++)
                a[i][j] = a[0][idx[j]];
        }

        int ans = 0;
        int U = 1 << 6;
        for (int S = 1; S < U; S++)
        {
            int gcd[3]{};
            int sig = -1;
            for (int i = 0; i < 6; i++)
                if (S & (1 << i))
                {
                    sig = -sig;
                    for (int j = 0; j < 3; j++)
                        gcd[j] = Gcd(a[i][j], gcd[j]);
                }
            ans += vec[gcd[0]].size() * vec[gcd[1]].size() * vec[gcd[2]].size() * sig;
        }

        const auto& vx = vec[a[0][0]];
        const auto& vy = vec[a[0][1]];
        const auto& vz = vec[a[0][2]];
        all.clear();
        int i = 0, j = 0, k = 0;
        while (i < vx.size() || j < vy.size() || k < vz.size())
            if ((j >= vy.size() || (i < vx.size() && vx[i] <= vy[j])) &&
                (k >= vz.size() || (i < vx.size() && vx[i] <= vz[k])))
                all.push_back(Node(vx[i++], 0));
            else if (k >= vz.size() || (j < vy.size() && vy[j] <= vz[k]))
                all.push_back(Node(vy[j++], 1));
            else
                all.push_back(Node(vz[k++], 2));

        int countAll = CountAll();
        int same3 = 0;
        int pre2 = -1, pre1 = -1;
        for (const auto& t : all)
        {
            if (pre1 == pre2 && t.val == pre1)
                same3++;
            pre2 = pre1;
            pre1 = t.val;
        }

        int count_ = 1;
        int same2 = 0;
        for (i = 1; i < all.size(); i++)
        {
            if (all[i].val == all[i - 1].val)
                count_++;
            if (all[i].val != all[i - 1].val || i == all.size() - 1)
            {
                if (count_ == 2)
                {
                    int appear[3]{};
                    if (all[i].val != all[i - 1].val)
                        for (int j = 1; j <= 2; j++)
                            appear[all[i - j].type]++;
                    else
                        for (int j = 0; j < 2; j++)
                            appear[all[i - j].type]++;

                    if (!appear[0])
                        same2 += vx.size();
                    else if (!appear[1])
                        same2 += vy.size();
                    else if (!appear[2])
                        same2 += vz.size();
                }
                else if (count_ == 3)
                    same2 += countAll - 1;
                count_ = 1;
            }
        }

        printOut(map[triple] = (ans + same2 * 3 + same3 * 5) / 6);
    }
}

int main()
{
    run();
    return 0;
}

总结

这道题大体思路是对的：把所有情况算出来，减去算重的。但是一开始的那个思路算重的次数是不定的。突破点是减弱限制，把算重的次数确定，但是代价是要用容斥原理。所以这道题容斥的方法也很重要。