题解 CF1030D 【Vasya and Triangle】

[在我的blog里看](http://www.wjyyy.top/1770.html) ## 题意： 在$n\times m$的矩形中找出一个格点三角形，使得$S_\triangle=\frac{nm}k,k\ge 2$。 ## 题解： 首先这个题要求出在$n\times m$的矩形中，是否存在一个**格点三角形**，使得这个格点三角形的面积为$\frac{nm}k$。 如果我们直接构造，可能需要枚举的东西太多了，$n,m,k$都达到了$10^9$的数量级。但是我们可以发现题目中$k$一定$\ge 2$，那么如果能构造，就一定可以被装在这个$n\times m$的矩形中。因为$n\times m$的矩形最大可以装下$\frac{nm}2$的三角形。此时问题转化为能否构造出一个$\frac{nm}k$的格点三角形，注意这个题还需要**输出顶点方案**。 样例给出了一个合法的数据和一个不合法的数据，一开始感觉上下互质可能会出问题，但是这个题和质数貌似没有关系。但是和约分肯定有关，因此猜想：格点三角形的面积一定是$\frac 12$的倍数。也就是说，$\frac {nm}k$约分后，分母不是$1$就是$2$。 既然是三角形，由于初中老师教过割补法求平面直角坐标系中三角形的面积，那我们就证一下这个猜想。我们构造一个任意的格点三角形，那么这个格点三角形的面积可以表示为一个边与坐标轴平行的矩形，减去三个直角三角形，这三个直角三角形都满足直角边与坐标轴平行。  这个矩形的面积是一个整数，则三角形的面积为$S_\triangle=\frac{ab}2$。又因为在格点三角形中，$ab$是整数，所以$S_\triangle$一定是$\frac 12$的倍数。 证完这个东西，我们发现三角形就是可构造的了。设要求的三角形面积为$S=\frac t2,t\in \mathbb N^*$，那么我们只需要在这个$n\times m$的三角形中找出$a\le n,b\le m$使得$ab=2S=t$即可，此时$t$并不会爆`long long`。那么一定存在这样一组整数对$(a,b)$吗？答案是肯定的。 要证存在整数对$(a,b)\ \mathrm{St.}\ ab=\frac{2nm}{k},a\le n,b\le m$，且$\gcd(2nm,k)=k,k\ge 2$。那么由于$\gcd(2nm,k)=k$，除出来的结果是整数，不考虑分子上的$2$，则这个整数应该只含$n,m$的质因子，且$ab\le nm$。 ### 单独讨论分子上的$2$ * 如果满足$k|2$，则这个整数满足“只含$n,m$的质因子”，并且$ab\le nm$； * 如果$k\not|2$，则$k\ge 3$，但是满足$\gcd(2nm,k)=k$，可知$\frac{2nm}k<nm$，同时$k|nm$，让$ab=\frac 2k\cdot nm$，约掉之后就可以使$n$或$m$中至少一个减小。比方说$k=p_1p_2$，则$ab=2\cdot \frac {n}{p_1}\cdot \frac{m}{p_2}$，则$ab\le nm$。又因为$p_1\ge 2$或$p_2\ge 2$，且$ \frac {n}{p_1},\frac{m}{p_2}$都是整数，因此$p_1,p_2$中至少有一个满足$\frac{2n}{p_1}\le n$或$\frac {2m}{p_2}\le m$。虽然不一定满足“只含$n,m$的质因子”，但是多出来的只是一个$2$，它可以被$\frac 2k$中的$k$约掉，从而达到上一句话的情况，就可以用$a,b$来表示了。 最后需要得出答案，构造出一个**直角三角形**，直角边分别为$a,b$，如何枚举$(a,b)$呢？作为$S'=\frac{2nm}k$的约数，它的枚举复杂度为$\sqrt{S'}$，数量级是$10^9$，从$1$开始容易$TLE$，事实上良心的pretest10也卡掉了我的前两次提交。因为$a\le n,b\le m$，所以枚举起点应该在$\lfloor \frac{S'}{\max(n,m)}\rfloor$，以避免枚举“另一条边超过$\max(n,m)$”的情况。不过最后还是要稍微检验一下（防止写快了弄混…… 其实只要推出来面积一定是$\frac 12$的倍数，和最后一段的上下界优化就可以做题了。但是为了严谨~~和题解需要~~我还是证明了一下存在性…… ## Code： ```cpp #include<cstdio> #include<cstring> #include<cmath> long long n,m,k; long long gcd(long long a,long long b) { if(!b) return a; return gcd(b,a%b); } int main() { scanf("%I64d%I64d%I64d",&n,&m,&k); long long tt=n>m?n:m; int flag=(n>=m); k=k; long long t=n>m?n:m; n=n*m; long long tmp=gcd(n,k); n/=tmp; k/=tmp; if(k>2) { puts("NO"); return 0; } if(k==1) n*=2; long long up=sqrt(n)+1; for(int i=(n/tt)?(n/tt):1;i<=up;++i) if(n%i==0) if(n/i<=t) { n=n/i; m=i; break; } puts("YES"); puts("0 0"); if(flag) { printf("%I64d 0\n",n); printf("0 %I64d\n",m); } else { printf("%I64d 0\n",m); printf("0 %I64d\n",n); } return 0; } ```