上海计算机学会2023年12月月赛C++丙组T3数轴旅行
发布时间
阅读量：
阅读量
数轴旅行
内存限制: 256 Mb时间限制: 1000 ms
题目描述
你要开始一场数轴旅行，初始时，你所在的位置为 x=0 ，你想要去 x=d 位置。
给定 n 个整数a1,a2,...,an，表示每次你可以往左移动 ai 个单位或往右移动 ai 个单位。
请问，最终能否到达 x=d 位置？能则输出 Yes，不能输出 No。
输入格式
输入共两行：
第一行，两个整数 n,d
第二行，n 个正整数 a1,a2,...an
输出格式
输出能否达到最终目标位置。
数据范围
- 对于 30% 的数据，满足 1≤n≤10，1≤ai≤10，−20≤d≤20。
- 对于 60% 的数据，满足 1≤n≤103，1≤ai≤103，−104≤d≤104。
- 对于 100% 的数据，满足 1≤n≤105，1≤ai≤109，−109≤d≤109。
样例数据
输入:
2 -4
6 8
输出:
Yes
说明:
向左走两次6，再向右走一次8
输入:
2 5
6 8
输出:
No
解析：
若d能整除ai的最大公约数，则yes 否则no
详见代码：
#include <bits/stdc++.h>
using namespace std;
int n,d;
int k;
int gcd(int x,int y){//辗转相除法求最大公约数
if (y==0) return x;
return gcd(y,x%y);
}
int main() {
cin>>n>>d;
cin>>k;
for(int i=2;i<=n;i++){
int x;
cin>>x;
k=gcd(k,x);
}
if (d%k==0){
cout<<"Yes";
}else{
cout<<"No";
}
return 0;
}
全部评论 (0)
还没有任何评论哟~