[EOJ Monthly 2018.4] A. ultmaster 的小迷妹们

[EOJ Monthly 2018.4] A. ultmaster 的小迷妹们

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

1 1 2

Yes

1 2 2

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;
}