Solution of CodeFoces1008D Pave the Parallelepiped

Revision en1, by chenchonghan, 2018-07-16 06:55:24

题目大意 有一个A×B×C的长方体,将其分为a×b×c的小长方体若干块,且a≤b≤c,这样的(a,b,c)有多少组?

题解 及找有多少组(a,b,c),使得这三个数中,一个为A的因数,另外有一个为B的因数,还有一个为C的因数。

如果直接用推组合数公式,就很容易陷入容斥的恐怖细节WA 黑 洞之中。

考虑把所有因数分组,使得每一组的因数都不同,将其分为7组,用二进制状态s表示: 第1位为1表示这个因数为A的因数 第2位为1表示这个因数为B的因数 第3位为1表示这个因数为C的因数 如101表示这个数为A与C的公因数,但不是B的因数

用cnt[s]表示状态为s的因数的个数(求cnt可用暴力卡过,但也有更好的办法,可见代码) 枚举a,b,c的状态(可相同),然后用组合数求出每种情况,然后加起来就是答案 如a,b都为状态s1,c为状态s2,则需要从cnt[s1]中选2个,cnt[s2]中选1个,即C(cnt[s1]+2−1,2)×C(cnt[s2]+1−1,1) (枚举状态时要判断状态是否合法:这三个状态是否包含ABC的因数)

Translated by Baidu:

Subject matter

There is a cuboid of A * B * C, which is divided into small cuboid blocks of a * b * C, and a is less than B = C, so how many (a, B, and C) are there?

An explanation

And how many groups (a, B, c) are found, so that one of these three numbers is the factor of A, another factor is B, and another factor is C.

If we use the combination formula directly, we can easily fall into the WA black hole which is contained in the horror details.

Considering that all factors are grouped so that the factors of each group are different, they are divided into 7 groups: binary s.

The factor of first is 1 that represents the factor of A

The factor of second is 1 that represents the factor of B

The factor of third is 1 that represents the factor of C

If 101 indicates that this number is a common factor of A and C, it is not a factor of B.

Using cnt[s] to represent the number of factors that state is s (CNT can be used by violent cards, but there is a better way to see the code).

Enumerate the state of a, B, C (the same), then use the combinatorial number to find out each case, and then add up the answer.

For example, a and B are state S1 and C are state S2, then we need to select 2 from cnt[s1] and 1 from cnt[s2], that is C (cnt[s1]+2 1,2) x (C).

(enumerating the state to determine whether the state is legal: does the three states contain the factor of ABC?)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100005;

long long C(int n,int m)
{
    long long ret=1;
    for(int i=1;i<=m;i++)
        ret*=(n-i+1);
    for(int i=1;i<=m;i++)
        ret/=i;
    return ret;
}
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 gcd(int a,int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}

int n;
int q[MAXN],m;
int cnt[10],use[10];
int fac[MAXN];

int main()
{
//预处理因数个数
    for(int i=1;i<MAXN;i++)
        for(int j=i;j<MAXN;j+=i)
            fac[j]++;
    int T,X,Y,Z;
    scanf("%d",&T);
    long long ans;
    while(T--)
    {
        scanf("%d%d%d",&X,&Y,&Z);
        m=0;
        int xy=gcd(X,Y),yz=gcd(Y,Z),xz=gcd(X,Z);
        int xyz=gcd(xy,Z);
        //计算每种状态的因数个数
        cnt[7]=fac[xyz];//111
        cnt[6]=fac[yz]-fac[xyz];//110
        cnt[5]=fac[xz]-fac[xyz];//101
        cnt[4]=fac[Z]-fac[xz]-fac[yz]+fac[xyz];//100
        cnt[3]=fac[xy]-fac[xyz];//011
        cnt[2]=fac[Y]-fac[yz]-fac[xy]+fac[xyz];//010
        cnt[1]=fac[X]-fac[xy]-fac[xz]+fac[xyz];//001

        ans=0;
        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))//检查合法
                    {
                        memset(use,0,sizeof use);
                        use[a]++;use[b]++;use[c]++;
                        long long tmp=1;
                        for(int i=1;i<8;i++)
                            if(use[i])
                                tmp*=C(cnt[i]+use[i]-1,use[i]);//组合数计算
                        if(tmp>0)
                            ans+=tmp;
                    }

        printf("%I64d\n",ans);
    }

    return 0;
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English chenchonghan 2018-07-16 06:55:24 4107 Initial revision (published)