题意:
一个长度为n的数组a, \(a_i = gcd(b_i, b_{i + 1})\), 问是否存在这样的b数组能够构成a
思路:
总结:
gcd可以推导出lcm的规律，图片中的那个 >= 关系是代表要产生\(a_i\)，必须最优是要满足这个关系，但是不一定满足了这个关系就能达成目的
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);
#define endl '\n'
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
int T, n;
int a[MAXN], b[MAXN];
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b)
{
return a * b / gcd(a, b);
}
int main()
{
IOS; cin.tie(0), cout.tie(0);
cin >> T;
while (T--)
{
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
b[1] = a[1], b[n + 1] = a[n];
for (int i = 2; i <= n; ++i)
b[i] = lcm(a[i - 1], a[i]);
bool flag = true;
for (int i = 1; i <= n; ++i)
if (a[i] != gcd(b[i], b[i + 1]))
flag = false;
cout << (flag ? "YES" : "NO") << endl;
}
return 0;
}