You are given a rectangular parallelepiped with sides of positive integer lengths A, B and C.

Find the number of different groups of three integers (a, b, c) such that 1≤a≤b≤c and parallelepiped A×B×C can be paved with parallelepipeds a×b×c. Note, that all small parallelepipeds have to be rotated in the same direction.

For example, parallelepiped 1×5×6 can be divided into parallelepipeds 1×3×5, but can not be divided into parallelepipeds 1×2×3.

链接🔗

「CodeForces 1007B」Pave the Parallelepiped

题解

考虑将每个数的约数分组,然后再通过组合数学求出
nn个数中放回取mm个的不同方案数为 C(n,m)C(n,m)

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxd = 1e5+10;
long long C(int n,int m)
{
    long long ans = 1ll;
    for(int i=1;i<=m;i++) ans *= (n-i+1);
    for(int i=1;i<=m;i++) ans /= i;
    return ans;
}
int gcd(int x,int y)
{
    if(!y) return x;
    return gcd(y,x%y);
}
int fac[maxd];
void init()
{
    for(int i=1;i<maxd;i++)
        for(int j=i;j<maxd;j+=i)
            fac[j]++;
}
bool check(int a,int b,int c)
{
    if((a&1)&&(b&2)&&(c&4))
        return true;
    if((a&1)&&(c&2)&&(b&4))
        return true;
    if((b&1)&&(a&2)&&(c&4))
        return true;
    if((b&1)&&(c&2)&&(a&4))
        return true;
    if((c&1)&&(a&2)&&(b&4))
        return true;
    if((c&1)&&(b&2)&&(a&4))
        return true;
    return false;
}
int cnt[8],use[8];
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    int _;scanf("%d",&_);init();
    while(_--)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        int ab = gcd(a,b); int bc = gcd(b,c); int ac = gcd(a,c);
        int abc = gcd(ab,c);
        cnt[7] = fac[abc]; // abc
        cnt[6] = fac[ab] - fac[abc]; // ab
        cnt[5] = fac[ac] - fac[abc];  // ac
        cnt[4] = fac[a] -cnt[6] - cnt[5] - cnt[7];  // a (a - ab - ac - abc)
        cnt[3] = fac[bc] - fac[abc]; // bc
        cnt[2] = fac[b] - cnt[3] - cnt[6] - cnt[7];      // 010 (b - bc - ab - abc)
        cnt[1] = fac[c] - cnt[5] - cnt[3] - cnt[7];     
        // for(int i=1;i<=7;i++) printf("%d ",cnt[i]);
        // putchar(10);
        long long ans = 0ll;
        for(int a=1;a<8;a++)
            for(int b=a;b<8;b++)
                for(int c=b;c<8;c++)
                    if(check(a,b,c))
                    {
                        use[a]++,use[b]++,use[c]++;

                        long long now = 1ll;
                        for(int i=1;i<8;i++)
                            if(use[i]) now *= C(cnt[i]+use[i]-1,use[i]);
                        if(now)
                        //printf("%d %d %d %lld\n",a,b,c,now);
                        ans += now;
                        use[a]--,use[b]--,use[c]--;
                    }
        printf("%lld\n",ans);
    }

    return 0;
}