CF-Div1037

B题说要dp其实没有dp，对于休息的那天直接贪心算
C题是一个模拟，排序后合起来考虑时刻，高度（不要拆开模拟）
D题的提示是数据结构，题解使用了pair<int,pair<int,int>>

前几题的思路都是贪心算，我做的时候方法很不灵活，相关基础也没掌握好，笨笨的。需要大量练习。

E.G-C-D，Unlucky!

gcd有一个性质：
gcd(a,b)=1等价于gcd(a,kb)=1

▶

证明

Tutorial里边有打段的解释，其实还是围绕这个性质来的。
关键要知道s_n和p_n有公因子g （通过将g消去可以联系两个等式）
S_i = s_i / g
P_i = p_i / g
对于中间一个a_i来说，S_i 整除 a_i / g ， P_i 整除 a_i / g
(由上述的性质)
所以 a_i / g 既要和 p_i-1 / p_i 互质，又要和 s_i+1 / s_i 互质
令x = p_i-1 / p_i
y = s_i+1 / s_i
所以 a_i / g = k * x * y
令k=1即可得出 a_i = g * x * y 这里就可以算出每一个可行的解

这个可行解能存在的条件可以是gcd(x,S_i)=1且gcd(y,P_i)=1
即
gcd(p[i-1],lcm(s[i],p[i]))=p[i]
gcd(s[i+1],lcm(s[i],p[i]))=s[i]

#include <bits/stdc++.h>
using namespace std;
main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		long long a[n + 1];
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		long long b[n + 1];
		for (int i = 1; i <= n; i++) {
			cin >> b[i];
		}
		long long ans[n + 1];
		for (int i = n; i >= 1; i--) {
			ans[i] = lcm(a[i], b[i]);
		}
		bool ch = 1;
		if(ans[1] != a[1]) ch = 0;
		if(ans[n] != b[n]) ch = 0;
		for (int i = 2; i <= n; i++) {
			if (__gcd(a[i - 1], ans[i]) != a[i]) {
				ch = 0;
			}
		}
		for (int i = n - 1; i >= 1; i--) {
			if (__gcd(b[i + 1], ans[i]) != b[i]) {
				ch = 0;
			}
		}
		if (ch) {
			cout << "YES" << "\n";
		} else {
			cout << "NO" << "\n";
		}
	}
}