Gym - 101341D是什么健身器材？
- 内容介绍
- 文章标签
- 相关推荐
本文共计607个文字，预计阅读时间需要3分钟。
青蛙生活在一维世界的原点，坐标为0。它需要到达坐标为x的点。由于某种原因，青蛙不能跳任意长度的距离，只能跳a1，a2，...，an这样的固定长度，并且可以向任何方向跳跃。
A frog lives in a one-dimensional world in the point with the coordinate 0. He needs to get to the point with the coordinate x. For some reason he cannot make jumps of arbitrary length, and can jump only by a1, …, an in any direction. Is he able to reach x?
Input
The first line contains two integers n and x separated by a space (1 ≤ n ≤ 200000, - 109 ≤ x ≤ 109) — the number of variants of jump length and the coordinate of the point to reach.
The second line contains n integers ai separated by spaces (1 ≤ ai ≤ 109) — the lengths of jumps the frog can make.
Output
Output «YES» (without quotes), if the frog can reach the point x, otherwise output «NO» (without quotes).
Examples
Input
3 17
3 5 4
Output
YES
Input
4 5
10 20 30 40
Output
NO
思路：
即求解方程组，且必须有整数解；
考虑两个的情况，即 ax+by=c;
此时c % gcd(a,b)才有解；
同理推广到多元即可；
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 200005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;
#define pi acos(-1.0)
ll quickpow(ll a, ll b) {
ll ans = 1;
while (b > 0) {
if (b % 2)ans = ans * a;
b = b / 2;
a = a * a;
}
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
int a[maxn];
int main() {
int n, k;
cin >> n >> k;
int i, j;
if (n == 1) {
int x;
cin >> x;
if (k%x != 0) {
cout << "NO" << endl;
}
else cout << "YES" << endl;
}
else {
cin >> a[0] >> a[1];
int Gcd = gcd(a[0], a[1]);
for (i = 2; i < n; i++) {
cin >> a[i];
Gcd = gcd(Gcd, a[i]);
}
if (k%Gcd != 0)cout << "NO" << endl;
else cout << "YES" << endl;
}
return 0;
}
本文共计607个文字，预计阅读时间需要3分钟。
青蛙生活在一维世界的原点，坐标为0。它需要到达坐标为x的点。由于某种原因，青蛙不能跳任意长度的距离，只能跳a1，a2，...，an这样的固定长度，并且可以向任何方向跳跃。
A frog lives in a one-dimensional world in the point with the coordinate 0. He needs to get to the point with the coordinate x. For some reason he cannot make jumps of arbitrary length, and can jump only by a1, …, an in any direction. Is he able to reach x?
Input
The first line contains two integers n and x separated by a space (1 ≤ n ≤ 200000, - 109 ≤ x ≤ 109) — the number of variants of jump length and the coordinate of the point to reach.
The second line contains n integers ai separated by spaces (1 ≤ ai ≤ 109) — the lengths of jumps the frog can make.
Output
Output «YES» (without quotes), if the frog can reach the point x, otherwise output «NO» (without quotes).
Examples
Input
3 17
3 5 4
Output
YES
Input
4 5
10 20 30 40
Output
NO
思路：
即求解方程组，且必须有整数解；
考虑两个的情况，即 ax+by=c;
此时c % gcd(a,b)才有解；
同理推广到多元即可；
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 200005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;
#define pi acos(-1.0)
ll quickpow(ll a, ll b) {
ll ans = 1;
while (b > 0) {
if (b % 2)ans = ans * a;
b = b / 2;
a = a * a;
}
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
int a[maxn];
int main() {
int n, k;
cin >> n >> k;
int i, j;
if (n == 1) {
int x;
cin >> x;
if (k%x != 0) {
cout << "NO" << endl;
}
else cout << "YES" << endl;
}
else {
cin >> a[0] >> a[1];
int Gcd = gcd(a[0], a[1]);
for (i = 2; i < n; i++) {
cin >> a[i];
Gcd = gcd(Gcd, a[i]);
}
if (k%Gcd != 0)cout << "NO" << endl;
else cout << "YES" << endl;
}
return 0;
}