codeforces 1030D

xiaoxiao2021-03-01  14

考场上rols告诉了我一个结论,就是2*n*m%k!=0就false,否则一定有解,于是我脑补了一个神奇的做法过了pretest,然后快乐FST,悲伤掉分,后来思考了一蛤发现那个神奇做法是sqrt(2*n*m/k)的复杂度,我当时还以为是log,我虽然有个二分让x,y先都小于n,m,不过可能还是不够优秀,于是T掉了。

一看题解,他说三角形是整点的面积一定是整数,我用初中的垂线法算了一蛤,发现area=2*n*m/k=y1x2+y2x3+y3x1-y1x3-y2x1-y3x2。全是整数乘法和加减,确实2*n*m/k一定是整数,哇,我以前怎么没留意过这个结论,别人怎么都知道,可能因为我没做过计算几何?菜哭.jpg

然后关于x*y=2*n*m/k,先直接让x=2*n/gcd(2*n,k),y=m/(k/gcd(2*n,k)),也就是y=2*n*m/k/x,然后因为这里有个2的影响,所以要判断一蛤是否越界,越界就把越界那个/2,没越界那个乘2

#include<cstdio> #include<cstring> long long n,m,k,st,ans,x,y; long long gcd(long long a,long long b) { if(!b) return a; else return gcd(b,a%b); } int main() { bool flag=true; scanf("%lld%lld%lld",&n,&m,&k); if((2*n*m)%k!=0) flag=false; long long area=2*n*m/k; x=2*n/gcd(2*n,k); y=area/x; if(x>n) x>>=1,y<<=1; if(flag) { puts("YES"); printf("%lld 0\n",x); printf("0 0\n"); printf("0 %lld\n",y); } else puts("NO"); }

 

转载请注明原文地址: https://www.6miu.com/read-4050309.html

最新回复(0)