Time limit per test: 2.0 seconds
Memory limit: 256 megabytes
ultmaster 男神和他的小迷妹们准备躺在图书馆前大草坪享受惬意的午后。
有强迫症的 ultmaster 想要使得自己和小迷妹们正好躺成一块完整的正方形，ultmaster 想知道能否挑出一些小迷妹（至少一个）实现他的愿望。
已知 ultmaster 的形状 n×n 的正方形，小迷妹的形状为 x×y 的长方形（可以横着或者竖着躺）。若能够则输出Yes 否则输出 No。
P.S. ultmaster 是正方形因为他比较肥。
Input
第一行三个整数 n,x,y (1≤n,x,y≤109) 分别表示描述中的 n,x,y。
Output
输出一行字符串，Yes 或 No 表示 ultmaster 能否实现他的愿望。
Examples
input
1 1 2
output
Yes
input
1 2 2
output
No
Note
样例一：可以构成 3×3 的正方形。
题解：直接判断gcd(x,y)能否整除n即可。
证明：考虑小正方形所在列，一定不能被gcd整除，小正方形所不在列，一定能被gcd整除，所以一定不能拼成大正方形。
如果能被gcd整除，则由扩展欧几里得一定存在ax−by=n，因此可以构成n×n在中间，四个ax×by在周围的正方形。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<stack>
#define ll unsigned long long
using namespace std;
const int maxn = 1e5+7;
ll n, x, y;
ll gcd(ll a, ll b) {
if(!b) return a;
else return gcd(b, a%b);
}
int main()
{
ll maxl = 0;
bool f = false;
scanf("%lld%lld%lld", &n, &x, &y);
if(n%gcd(x,y) == 0) puts("Yes");
else puts("No");
return 0;
}
版权声明：本文为weixin_39792252原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。