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
题解
考虑将每个数的约数分组,然后再通过组合数学求出
个数中放回取个的不同方案数为
代码
#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;
}