错了一个小地方调了一晚上。。。。
题目大意：
给出最多2E+5种不同的矩形，每种有它的长h和宽v还有数量d，现在你要构造大矩形，使得在上面沿着平行于长或宽的边划刀，切出来的矩形正好是给出的所有矩形。问你能构造几种不同的大矩形。其中给出的矩形不能旋转。大矩形亦不能旋转，这意味着长为A，宽为B的大矩形和长为B，宽为A的大矩形不同。
题目分析：
首先我们令矩形的总数目为tot。那么横着切p刀，竖着且q刀，则(p+1)(q+1)=tot。为了简便，下文的p表示横着切了p-1刀，q表示竖着切了q-1刀。
以此为突破口，不难证明对于一组(p,q)，矩形的大小固定。那么一组(p,q)可以作为大矩形的条件是什么?
为了得到这个结论，我们设xi表示所有hi相同的矩形的数量，共m种不同的hi。我们不难发现xi是p的倍数。
理由是这样子的：若xi不是p的倍数，那么在划分后必然在大矩形内有多余的长为hi的小矩形，这样必定非法。所以上面的结论得证！
由于上面的理由，我们不难发现所有的hi相同的矩形必然集中在一坨，贯穿上下。即如果一列有一个是hi，那么一整列都是hi。
现在我们解决了长上面的问题，还有宽没解决。
首先我们发现如果一个v没有对应所有存在的h，那么这个必然无解。理由也很简单，一开始我安排好了p，现在安排q的时候受p的影响。
同样的我们还能得出两个结论，一是任意的xi/p必然是v的因数，理由和上面相同；二是对于相同的v，它们占的行数相同，这个也很容易想到。
现在我们通过对h和v的分析，得到了一个比较简单的O(n*sqrt(Σd))的算法，经过计算会发现超时，想办法解决这个问题。
首先xi是p的倍数意味着p一定是xi的因数，这样p一定是所有xi的因数，也就是说p是所有xi的最大公因数的因数，我们解决了h上的问题。
考虑v上的第一个结论如何优化，xi/p必然是v的因数。意味着我们可以找到一个si使得gcd(qi,v)=si，接着p一定是qi/si的倍数。所以p是所有qi/si的最小公倍数的倍数。这个可以通过唯一分解定理证明。
至于v上的第二个结论，首先写出式子，推导后发现这是一个可以预判的式子，预处理的时候直接搞定。
这样我们得到了一个O(sqrt(Σd))的算法。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 #define mp make_pair 5 6 typedef long long ll; 7 typedef long double ld; 8 9 const int maxn = 205000; 10 11 int n,m; 12 struct node{ll h,v,d;}mt[maxn]; 13 vector <pair<ll,ll> > V[maxn]; 14 ll rt[maxn],tot; 15 ll mx; 16 ll zzll=1; 17 18 void init(){ 19 for(int i=1,now=0;i<=n;i++){ 20 if(mt[i].h == mt[now].h){V[m].push_back(mp(mt[i].v,mt[i].d));rt[m]+=mt[i].d;} 21 else{now = i; m++; V[m].push_back(mp(mt[i].v,mt[i].d)); rt[m]+=mt[i].d;} 22 } 23 } 24 25 void read(){ 26 scanf("%d",&n); 27 for(int i=1;i<=n;i++){ 28 scanf("%lld%lld%lld",&mt[i].h,&mt[i].v,&mt[i].d); tot += mt[i].d; 29 } 30 sort(mt+1,mt+n+1,[](node a,node b){return a.h==b.h?a.v<b.v:a.h<b.h;}); 31 init(); 32 } 33 34 int NoSolution(){ 35 int hh = V[1].size(); 36 for(int i=2;i<=m;i++) if(V[i].size()!=hh){return 1;} 37 for(int i=0;i<hh;i++){ 38 ll kk = V[1][i].second; 39 for(int j=2;j<=m;j++){ 40 ll jj = V[j][i].second; 41 if(V[j][i].first != V[1][i].first){return 1;} 42 if((ld)kk/(ld)rt[1] != (ld)jj/(ld)rt[j]){return 1;} 43 } 44 } 45 for(int i=1;i<=m;i++){ 46 for(int j=0;j<V[i].size();j++){ 47 ll mm = __gcd(rt[i],V[i][j].second); 48 mm = rt[i]/mm; 49 ll pp = __gcd(zzll,mm); 50 zzll = (zzll/pp)*mm; 51 if(zzll > mx){return 1;} 52 } 53 } 54 return 0; 55 } 56 57 ll ans = 0; 58 void solve(ll ht,ll kd){ 59 if(ht % zzll == 0){ans ++;} 60 } 61 62 void work(){ 63 mx = rt[1]; 64 for(int i=2;i<=m;i++) mx = __gcd(mx,rt[i]); 65 if(NoSolution()){puts("0");return;} 66 for(ll i=1;i*i<=mx;i++){ 67 if(mx % i != 0) continue; 68 solve(i,tot/i); 69 if(i*i==mx)break; 70 solve(mx/i,tot/(mx/i)); 71 } 72 printf("%lld",ans); 73 } 74 75 int main(){ 76 read(); 77 work(); 78 return 0; 79 }