【题目来源】

洛谷：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:Y=16:9X:Y=16:9.

有一张宽度为X XX像素、高度为Y YY像素的图片。请判断其宽高比是否为16 : 9 16:916:9，即是否满足X : Y = 16 : 9 X:Y = 16:9X:Y=16: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

【核心思想】

1. 问题分析：给定图片宽度X XX和高度Y YY，需要判断宽高比是否为16 : 9 16:916:9。即是否存在正整数k kk，使得X = 16 k X = 16kX=16k且Y = 9 k Y = 9kY=9k。等价于判断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。

2. 算法选择：

   • 欧几里得算法（辗转相除法）：计算X XX和Y YY的最大公约数g = gcd ⁡ ( X , Y ) g = \gcd(X,Y)g=gcd(X,Y)
   • 比例化简判定：将X XX和Y YY同时除以g gg得到最简比，检查是否等于16 : 9 16:916:9

3. 关键步骤：

   • 读取输入：X XX（宽度）、Y YY（高度）
   • 计算gcd ⁡ \gcdgcd：t = gcd ⁡ ( X , Y ) t = \gcd(X, Y)t=gcd(X,Y)
   • 判定比例：
     • 若16 × t = X 16 \times t = X16×t=X且9 × t = Y 9 \times t = Y9×t=Y，输出Yes
     • 否则输出No
   • 等价于检查X t = 16 \frac{X}{t} = 16tX​=16且Y t = 9 \frac{Y}{t} = 9tY​=9

4. 时间/空间复杂度：

   • 时间复杂度：O ( log ⁡ min ⁡ ( X , Y ) ) O(\log \min(X, Y))O(logmin(X,Y))，辗转相除法的复杂度
   • 空间复杂度：O ( 1 ) O(1)O(1)，仅使用常数个变量

5. 欧几里得算法判定比例的核心思想：

   • 最简比唯一性：任意两个正整数的比可以唯一表示为最简分数形式，通过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:Y=16:9⇔9X=16Y，也可通过交叉相乘判定，但gcd ⁡ \gcdgcd方法同时适用于更复杂的比例验证场景
   • 辗转相除的高效性：欧几里得算法通过取模运算快速缩小问题规模，时间复杂度为对数级别，远优于枚举
   • 适用于比例判定、分数化简、有理数比较等基础数论问题

【算法标签】

#入门 #欧几里得算法

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intx,y;// x: 图片宽度, y: 图片高度// 辗转相除法求最大公约数（GCD）intgcd(inta,intb){returnb?gcd(b,a%b):a;}intmain(){cin>>x>>y;// 读入图片的宽度和高度intt=gcd(x,y);// 计算 x 和 y 的最大公约数// 判断化简后的比例是否为 16:9// 若 x:y = 16:9，则 x = 16*k, y = 9*k（k 为某个正整数）// 即 x/gcd(x,y) = 16 且 y/gcd(x,y) = 9// 等价于 16*t == x 且 9*t == y（其中 t = gcd(x,y)）if(16*t==x&&9*t==y)cout<<"Yes"<<endl;// 宽高比为 16:9elsecout<<"No"<<endl;// 宽高比不为 16:9return0;}

【运行结果】

800 450 Yes