引言：

本来，今天我是想着出俩题或三题题解的，但是在打第一题的时候就天塌了，导致今天就只搓了一道题，这题的难度在CF中为1300的水准，但我感觉这题的难度实则不止1300，因为前几天1400的题里，都没有遇到这么棘手的，可能是我数学方面的能力不足，以至于这题耗费我巨大心力，而且，最恶心的是，这题的题目翻译还翻译错了，导致我找错误找半天都没找出来，具体下面会讲，接下来，我们进入今天的题目讲解----------->

MEX Count

接下来，我们先来看题目

题意分析

这是题目的链接Problem - 2124C - Codeforces

不想跳转的可看下图

看完题目后，是不是很抽象，第一行就看不懂了，所以我又用了别的翻译插件来翻译这个题目，如图

看这个翻译是不是很明显，就是ａi可以整除ａi+1，但好巧不巧，这个翻译也是错的，所以我遭不住了，题目的实际意思其实是，一个数组a，这个数组是i+1位置下的元素可以整除i位置下的元素

那么，这个弄清楚后，后面的翻译就没问题了，很清晰，就是对a数组进行操作，给定一个变量x，然后对a数组中的元素乘任意个数的x，得到一个新的数组b

题目输入的就是这个数组b，然后让我们求出可能得x中的任意一个值即可

那么，题目就讲解完了，接下来我们进行逻辑梳理

逻辑梳理

首先，我们先来分析下a数组和b数组的区别

同一个下标下，b数组的元素是由a数组元素乘上未知个x得到的，因为是对a数组的元素进行乘的操作，所以b数组整体的最大公因数肯定不会低于a数组的最大公因数

我们再来思考下还有啥能找的现成的，那就还有相邻下标下a元素变成b元素的方式若不同对公因数的影响

第一种　ｉ　下标的a元素和ｉ＋１下标下的ａ元素都不乘ｘ，这时这俩个的公因数无变化

第二种　ｉ　下标的ａ元素乘了ｘ，ｉ＋１下标下的ａ元素没乘ｘ。或反之，这种情况下，俩个的公因数亦没有变化

第三种　ｉ和ｉ＋１下标下的ａ元素都乘了ｘ，这时候，公因数就会变大了

那么，通过这三种情况，我们先来假设第一种情况

ｂ数组如果本来就是ａ数组，那么这个时候因为ａ数组中临近的下一个元素总是他前面元素的倍数，所以我们可以从后往前进行遍历，通过一次次的迭代最小公约数，然后寻找最大公倍数来得到可能得ｘ。讲起来很抽象，那么，我们来通过图文来理解

如图。因为现在是第一种情况，所以ａ数组的数据即为ｂ数组的数据，那么，我们将ａｉ与ａｉ＋１的元素进行取最大公因数，得到的就是ａｉ，然后我们再将上一次得到的最小公倍数与ａｉ／现在的最大公因数　这俩个数进行求最小公倍数的操作得到一个新的最小公倍数（这个即到目前为止，不看前面的元素，可以使用的最小的ｘ）

这种我们可以把他当做是那种将一个大份的元素拆解成一个个小份的元素进行一次次演算，得到每次的最佳值，再用最佳值去进行操作即可，直到走到底部为止

那为什么进行先前最小公倍数与ａｉ／现在的最大公因数来求这次的最小公倍数这个操作得到的最小公倍数就是满足条件的值呢，那我们来徐徐道来

先前的最小公倍数即只管后面那些数组时，ｘ的最小值

ａｉ／现在的最大公因数即该下标下的这个元素的剩余的因数

如果想要乘任意次来达到数据的变化条件，就需要得到上面俩个数据的最小公倍数，这样就可以使加上当前下标后的数组也满足使用ｘ来达到现在的ｂ数组

所以就一路推下去就好了

其余俩种情况也是同理，原理我上面也讲的差不多了，太过玄乎了，所以这里就不展开讲了，这个的逻辑是否完全准确我也没有把握，但是我把我能想到的情况都推敲了下，都没什么问题，代码也ＡＣ了，接下来，逻辑梳理讲完了，我们来进入代码实现的环节。

代码实现

上面的逻辑理清楚后，代码实现其实就很简单了，只需要打一个求最大公约数的函数和一个求最小公倍数的函数就可以了，然后再循环里调用一下就好了，gcd函数为最大公约数，lcm函数为最小公倍数，求这俩个数的函数应该都会实现吧，这里就不讲了，接下来就上AC源代码啦

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <queue>
#include <vector>
using namespace std;int t;
long long a[600010];long long gcd(long long x, long long y)
{if (y == 0)return x;return gcd(y, x % y);
}long long lcm(long  long x,long long y)
{long long k = gcd(x, y);return x / k * y;
}void solve()
{long long Gcd = 0;long long Lcm = 1;int n;a[0] = 1;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = n; i > 0; i--){Gcd = gcd(Gcd, a[i]);Lcm = lcm(Lcm, a[i] / Gcd);}cout << Lcm << endl;
}int main()
{cin >> t;while (t--){solve();}return 0;
}

那么，这题就讲完啦