题目概述

求有多少个小长方体 $(a,b,c),a\le b\le c$ 能够拼成大长方体 $(A,B,C)$ 。

解题报告

其实就是求有多少个 $(a,b,c)$ 满足其中一个是 $A$ 的因子另一个是 $B$ 的因子剩下那个是 $C$ 的因子。

但是 $a,b,c$ 需要有序，我们要想办法去重。你可以大力讨论。

一种比较好(Copy翻译)的方法：给每个数一个二进制状态 $s$ ，$s$ 第 $0$ 位代表这个数是不是 $A$ 的因子，第 $1$ 位代表这个数是不是 $B$ 的因子，第 $2$ 位代表这个数是不是 $C$ 的因子。这样总共有 $7$ 种状态，每种状态满足的数都可以容斥出来。

然后只需要爆枚 $i,j,k$ 表示 $a,b,c$ 是什么状态，如果 $i,j,k$ 满足题目要求就可以加上这种情况的方案数了：

1. 三种状态都不一样：直接乘法原理。
2. 有两个状态一样：相同的状态使用可重复的组合数公式( $n$ 个里选出 $m$ 个可重复选的方案数为 $n+m-1\choose m$ ，感性理解：有 $m-1$ 个虚拟物品表示选的和上一次一样)，然后乘法原理。
3. 三个状态都一样：使用可重复的组合数公式。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000;

int te,A,B,C,num[maxn+5],AB,AC,BC,ABC,sum[8];LL ans;

int gcd(int a,int b) {return b?gcd(b,a%b):a;}
inline bool check(int i,int j,int k) {return (i&1)&&(j&2)&&(k&4);}
inline LL C3(LL x) {return x*(x-1)*(x-2)/6;}
inline LL C2(LL x) {return x*(x-1)/2;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (int i=1;i<=maxn;i++) for (int j=i;j<=maxn;j+=i) num[j]++;
    for (scanf("%d",&te);te;printf("%lld\n",ans),ans=0,te--){
        scanf("%d%d%d",&A,&B,&C);AB=gcd(A,B);AC=gcd(A,C);BC=gcd(B,C);ABC=gcd(AB,C);
        sum[1]=num[A]-num[AB]-num[AC]+num[ABC];sum[2]=num[B]-num[AB]-num[BC]+num[ABC];sum[3]=num[AB]-num[ABC];
        sum[4]=num[C]-num[AC]-num[BC]+num[ABC];sum[5]=num[AC]-num[ABC];sum[6]=num[BC]-num[ABC];sum[7]=num[ABC];
        for (int i=1;i<8;i++)
            for (int j=i;j<8;j++)
                for (int k=j;k<8;k++)
                    if (check(i,j,k)||check(i,k,j)||check(j,i,k)||check(j,k,i)||check(k,i,j)||check(k,j,i))
                        if (i==j&&j==k) ans+=C3(sum[i]+2); else if (i==j) ans+=C2(sum[i]+1)*sum[k];
                        else if (j==k) ans+=C2(sum[j]+1)*sum[i]; else ans+=(LL)sum[i]*sum[j]*sum[k];
    }return 0;
}