题解：洛谷 AT_abc463_a [ABC463A] 16:9

【题目来源】洛谷AT_abc463_a [ABC463A] 16:9 - 洛谷【题目描述】There is an image with a width ofX XXpixels and a height ofY YYpixels. Determine whether the ratio of the width to the height is16 1616to9 99, that is, whetherX : Y 16 : 9 X:Y16:9X:Y16:9.有一张宽度为X XX像素、高度为Y YY像素的图片。请判断其宽高比是否为16 : 9 16:916:9即是否满足X : Y 16 : 9 X:Y 16:9X:Y16:9。【输入】The input is given from Standard Input in the following format:X XXY YY【输出】If the ratio of the width to the height is16 1616to9 99, outputYes; otherwise, outputNo.【输入样例】800 450【输出样例】Yes【核心思想】问题分析给定图片宽度X XX和高度Y YY需要判断宽高比是否为16 : 9 16:916:9。即是否存在正整数k kk使得X 16 k X 16kX16k且Y 9 k Y 9kY9k。等价于判断X gcd ⁡ ( X , Y ) 16 \frac{X}{\gcd(X,Y)} 16gcd(X,Y)X​16且Y gcd ⁡ ( X , Y ) 9 \frac{Y}{\gcd(X,Y)} 9gcd(X,Y)Y​9。算法选择欧几里得算法辗转相除法计算X XX和Y YY的最大公约数g gcd ⁡ ( X , Y ) g \gcd(X,Y)ggcd(X,Y)比例化简判定将X XX和Y YY同时除以g gg得到最简比检查是否等于16 : 9 16:916:9关键步骤读取输入X XX宽度、Y YY高度计算gcd ⁡ \gcdgcdt gcd ⁡ ( X , Y ) t \gcd(X, Y)tgcd(X,Y)判定比例若16 × t X 16 \times t X16×tX且9 × t Y 9 \times t Y9×tY输出Yes否则输出No等价于检查X t 16 \frac{X}{t} 16tX​16且Y t 9 \frac{Y}{t} 9tY​9时间/空间复杂度时间复杂度O ( log ⁡ min ⁡ ( X , Y ) ) O(\log \min(X, Y))O(logmin(X,Y))辗转相除法的复杂度空间复杂度O ( 1 ) O(1)O(1)仅使用常数个变量欧几里得算法判定比例的核心思想最简比唯一性任意两个正整数的比可以唯一表示为最简分数形式通过gcd ⁡ \gcdgcd约分后得到。若最简比等于16 : 9 16:916:9则原比必为16 : 9 16:916:9的某个整数倍避免浮点误差不直接计算X Y \frac{X}{Y}YX​并与16 9 \frac{16}{9}916​比较可能产生浮点精度问题而是利用整数运算和gcd ⁡ \gcdgcd进行精确判定等价变形技巧X : Y 16 : 9 ⇔ 9 X 16 Y X:Y 16:9 \Leftrightarrow 9X 16YX:Y16:9⇔9X16Y也可通过交叉相乘判定但gcd ⁡ \gcdgcd方法同时适用于更复杂的比例验证场景辗转相除的高效性欧几里得算法通过取模运算快速缩小问题规模时间复杂度为对数级别远优于枚举适用于比例判定、分数化简、有理数比较等基础数论问题【算法标签】#入门 #欧几里得算法【代码详解】#includebits/stdc.husingnamespacestd;intx,y;// x: 图片宽度, y: 图片高度// 辗转相除法求最大公约数GCDintgcd(inta,intb){returnb?gcd(b,a%b):a;}intmain(){cinxy;// 读入图片的宽度和高度inttgcd(x,y);// 计算 x 和 y 的最大公约数// 判断化简后的比例是否为 16:9// 若 x:y 16:9则 x 16*k, y 9*kk 为某个正整数// 即 x/gcd(x,y) 16 且 y/gcd(x,y) 9// 等价于 16*t x 且 9*t y其中 t gcd(x,y)if(16*tx9*ty)coutYesendl;// 宽高比为 16:9elsecoutNoendl;// 宽高比不为 16:9return0;}【运行结果】800 450 Yes