上海计算机学会2023年12月月赛C++丙组T3数轴旅行¶
keywords: 数学
题目链接¶
题目描述¶
初始位于数轴原点，有 n 个数，表示每次可以向左或者向右移动 �� 步，移动步数不限。即，可以向左连续移动 3 个 �� 步，再向右移动 1 个 �� 步。问最终，是否可以落到坐标 d 上
解题思路¶
题面描述没有说 �� 只能走一步，但读题看起来是走一步的样子。但是样例分析，“向左走两次6，再向右走一次8”，这就说明，可以随便走。如果用模拟的话，那时间复杂度是比指数级别还大的，无法通过此题。 把这个每一个步长当成方程的系数，那么未知数就是每一次走了几步，即，多元一次方程。问题转换成，判定多元一次方程是否有解的问题。 ，有整数解，等价于，�1�1+�2�2+...+����=�，有整数解，等价于，(�1,�2,...,��)|� 即，所有系数的最大公约数是否可以整除 N
代码¶
#include <bits/stdc++.h>
using namespace std;
int n, d;
int a, b;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
cin >> n >> d;
cin >> a;
n--;
while (n--) {
scanf("%d", &b);
a = gcd(a, b);
}
if (d % a == 0) cout << "Yes";
else cout << "No";
return 0;
}
总结¶
这个有解的证明过程，确实不知道，得查一下。 把“人工语言”转换成“形式语言”，是这道问题考察的要点