目錄
?
引言：
G-C-D, Unlucky!
? ? ? ? 題意分析
? ? ? ? 邏輯梳理
? ? ? ? 代碼實現
結語：
?
引言：
? ? ? ? 因為今天打了個ICPC網絡賽，導致坐牢了一下午，沒什么時間打題目了，就打了一道題，所以，今天我們就只講一題了，該題是CF難度分值1400的題，今天應該是跟第一天一樣輕松的訓練量，那話不多說，我們進入題目講解————>
?????????????????????????????????????????????????????????????????????
G-C-D, Unlucky!
? ? ? ? 與先前一樣。我們先來看題目
? ? ? ? 題意分析
? ? ? ? 這是題目的鏈接Problem - E - Codeforces
? ? ? ? 不想跳轉的可以看下圖
????????
? ? ? ? 這個題目表達的意思其實是很簡單的，就是輸入2個數組，然后問是否存在一個數組a，滿足，第一個數組是a數組從前往后求公約數，第二個數組是a數組從后往前求公約數，那么，題目意思就說完了，接下來我們來梳理一下邏輯
? ? ? ? 邏輯梳理
? ? ? ? 首先一個是從前往后依次公約數的數組，這個數組的第一個一定是a數組的首元素
? ? ? ? 還有一個是從后往前依次公約數的數組，這個數組的最后一個元素一定是a數組的尾元素
? ? ? ? 這個是第一眼就能看出的東西，但我感覺對這題沒有什么用，但是，第一個數組的最后一個元素與第二個數組的首元素反而非常關鍵
? ? ? ? 因為第一個數組的末元素是將a數組全部進行求公約數，第二個數組的首元素是將a數組全部進行求公約數，只是一個是順著求，一個是逆著求
? ? ? ? 所以，若這個a數組存在，那么第一個數組的末元素和第二個數組的首元素一定要相等，這是第一個若要讓a數組存在需要滿足的條件
? ? ? ? 那么，接下來，因為第一個數組是從前往后求公約數，所以第一個數組從前往后要單調不遞增，因為第二個數組是從后往前求公約數，所以第二個數組從后往前要單調不遞增，即從前往后要單調不遞減，這是第二個若要讓a數組存在需要滿足的條件
? ? ? ? 然后，既然已經知道了數的變化順序，接下來，我們來看變化規律，因為是一步步公約數求下去的，所以對第一個數組而言，i+1位置上的數肯定是i位置上數的因數或本身而不能是其他的數，若是其他的數就不滿足依次求公約數的性質了
? ? ? ? 對第二個數組也同理，只是第二個數組是從后往前求公約數，所以i位置上的數肯定是i+1位置上的數的因數或者他本身而不能是其他的數
? ? ? ? 上邊的便是第三個若要讓a數組存在需要滿滿足的條件，即第一個數組依次往后的數據要是他前一個數據的因數或本身，第二個數組依次往前的數據要是他后一個數據的因數或本身
? ? ? ? 還有一個就比較抽象了，這也是最難想的一個條件，這個條件我也想了好久，這個條件如圖
? ? ? ? 我們只需要通過一個循環求 下標為i的第一個數組的元素 和 下標為i+1的第二個數組的元素? 的最大公約數求出來判斷是否為第二個數組的第一個元素即可（因為這倆個元素求出來的公約數就是整個數組的公約數了）
? ? ? ? 那么，四個關鍵的條件就集齊啦，接下來我們就進入代碼實現的環節
? ? ? ? 代碼實現
? ? ? ? 邏輯已經講完了，接下來我們只需要用代碼將四個功能實現出來就可以了，那么具體我就不多講了，直接放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[100010];
long long b[100010];long long gcd(long long x, long long y)
{if (y == 0)return x;return gcd(y, x % y);
}void solve()
{int xixi = 0;int n;cin >> n;a[0] = 1e10;for (int i = 1; i <= n; i++){cin >> a[i];if (a[i] > a[i - 1])xixi = 1;}for (int i = 1; i <= n; i++){cin >> b[i];if (b[i] < b[i - 1])xixi = 1;}for (int i = 1; i < n; i++){if (a[i] % a[i + 1] || b[i + 1] % b[i]){xixi = 1;break;}if (gcd(a[i], b[i+1]) != b[1]){xixi = 1;break;}}if (n == 1 && a[1] == b[1]){cout << "Yes" << endl;return;}if (xixi || a[n] != b[1]){cout << "No" << endl;return;}cout << "Yes" << endl;
}int main()
{cin >> t;while (t--){solve();}return 0;
}? ? ? ? 那么這道題就講完啦
結語：
????????今日算法講解到此結束啦，希望對你們有所幫助，謝謝觀看，如果覺得不錯可以分享給朋友喲
?
