序列排序Ⅱ

原题题面

描述

ldz 交给你了一个 1~n 的排列，当某两个相邻的数字满足互质时，则可以交换这两个数字，请问你进行若干次交换后，能否将这个排列变为严格递增的。（即 1, 2, 3, 4... , n-1, n）

两个数字互质的定义：若两个数字的最大公约数为 1 时，即认为这两个数字互质。

输入

输入第一行包含一个正整数 n(1≤n≤105)。

接下来一行包含由空格隔开的 nn 个正整数，第i个整数记为 a_iai​，保证每个数字仅出现一次，且满足 (1≤a_i≤n)(1≤ai​≤n)。

输出

输出 "Yes" 代表可以使得序列有序，否则输出 "No"。(不要输出引号)

输入样例 1 

8
1 2 8 4 5 6 7 3

输出样例 1

No

提示

由于只能交换相邻的数字，所以无法使得排列递增。

解析

对于任意两个数……

让我们以样例的这组序列为例：1 2 8 4 5 6 7 3。

随便挑出两个数字，如8和6。显然，这8在前而6在后。也就是说，不管8和6如何运动，最终将会靠在一起并交换位置。显然，此时8和6并不互质，所以6无法移动位置至8前面。

理清思路

如上所述，若是两个数a和b满足以下3个条件：

1. a>b；
2. a在b前；
3. a和b不互质。

那么，如果在一个序列中只要有任意的如是两个数，该序列就无法满足题意。

基本实现

如果只根据以上思路，把序列双重循环地遍历，复杂度就到了O(n²)，显然会超时。然而，如果把不互质的所有数拎出来，就满足了第3个条件；另外要依次取出，就满足了第2个条件；最后只需对与这一个被拎出来的子序列进行遍历，如果发现有任意的a＞b，即满足了第1个条件，那么该序列就无法满足题意，输出No。

示例代码

#include
    <bits tdc++.h="">

using namespace std;
const int maxn=100005;
int n,a[maxn];
vector
     
       G[maxn];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		for(int j=2;j*j<=a[i];j++){
			if(a[i]%j==0){
				G[j].push_back(a[i]);
				G[a[i]/j].push_back(a[i]);
			}
		}
	}
	for(int i=2;i<=n;i++){
		for(int j=1;j
      <g[i].size();j++){ if(g[i][j]<g[i][j-1]){="" cout<<"no";="" return="" 0;="" }="" cout<<"yes";="" }<="" ode=""></g[i].size();j++){>
     
    </bits>

<p> </p>