题目概述

有 $n$ 种小矩形，第 $i$ 种小矩形长为 $w_i$ 宽为 $h_i$ ，有 $c_i$ 个，问有多少种 $(A,B)$ 使得存在一种切割方案将其切割为所有小矩形。

解题报告

神仙计数题，首先需要发现如果存在 $w_i,h_j$ 和 $w_j,h_j$ 却没有 $w_i,h_j$ 或没有 $w_j,h_i$ 就无解了，因为无法在不切开小矩形的前提下铺成一个大矩形。假设离散过后有 $A$ 种 $w$ 和 $B$ 种 $h$ ，那么还需要满足 $\forall i<A\land j<B,{c_{i,j}\over c_{i,j+1}}={c_{i+1,j}\over c_{i+1,j+1}}$ 。

然后我们可以枚举 $d$ 表示把 $w=1$ 的小矩形分成多少列，由于比例确定所以可以得到其他 $w$ 的小矩形的摆放方式。但 $d$ 需要满足是 $c_{i,j}$ 的因子，所以答案就是 $gcd(c_{1,1},c_{1,2},\cdots,c_{A,B})$ 的因子个数。

示例程序

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#define mp make_pair
using namespace std;
typedef long long LL;typedef long double DB;
const int maxn=200000;

int n,ans;LL a[maxn+5],b[maxn+5],GCD;map<pair<LL,LL>,LL> f;

LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
#define val(i,j) (f[mp((a[i]),(b[j]))])
inline DB fcmp(const DB &a,const DB &b) {if (fabs(a-b)<1e-8) return 0;return a<b?-1:1;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (int i=(scanf("%d",&n),1);i<=n;i++){
        LL x,y,z;scanf("%lld%lld%lld",&x,&y,&z);
        a[++a[0]]=x;b[++b[0]]=y;GCD=gcd(f[mp(x,y)]=z,GCD);
    }
    sort(a+1,a+1+a[0]);a[0]=unique(a+1,a+1+a[0])-a-1;
    sort(b+1,b+1+b[0]);b[0]=unique(b+1,b+1+b[0])-b-1;
    if (a[0]*b[0]!=n) return puts("0"),0;
    for (int i=1;i<=a[0];i++) for (int j=1;j<=b[0];j++) if (!val(i,j)) return puts("0"),0;
    for (int i=1;i<a[0];i++)
        for (int j=1;j<b[0];j++)
            if (fcmp((DB)val(i,j)/val(i,j+1),(DB)val(i+1,j)/val(i+1,j+1))) return puts("0"),0;
    for (int i=1,S=sqrt(GCD);i<=S;i++) if (!(GCD%i)) ans+=((LL)i*i<GCD)+1;return printf("%d\n",ans),0;
}