题解 AT2692 【[ABC070C] Multiple Clocks】
TRZ_2007
2020-11-24 16:17:34
**题解 [AT2692 【[ABC070C] Multiple Clocks】](https://www.luogu.com.cn/problem/AT2692)**
# Solution
这道题其他 dalao 们可能都认为太简单了就没有讲结论是怎么来的(~~不过的确是显然~~),所以先讲一下为什么是所有数的最小公倍数。
放开有 $n$ 个数字的情况,先看看有两个数字的情况。刚刚开始的思路肯定是很暴力的枚举每一个时间,看看两针是否重合,以 t[1] = 4,t[2] = 6 为例如图:
![](https://cdn.luogu.com.cn/upload/image_hosting/7th5ery2.png)
得出两个数字的结论之后,我们就可以轻易的得出最终的答案就是所有数字的最小公倍数。
但是还要注意一点,这题的数据范围有一点大,需要一些~~技巧~~。
~~最小公倍数总没有人不会求了吧~~
# Code
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N = 109;
ll a[N];
int n;
int main() {
scanf("%d",&n);
for(int i = 1;i <= n;i++) {
scanf("%llu",&a[i]);
}
for(int i = 2;i <= n;i++) {
a[i] = a[i] / __gcd(a[i],a[i - 1]) * a[i - 1];//注意,由于10^32还是超过了ull的最大范围,所以我们做的时候要先除后乘。
}
printf("%llu\n",a[n]);
return 0;
}
```