#723558 (C++14) No.1779 Magical Swap

• 問題: No.1779 Magical Swap
• ユーザー: XD
• 提出日時: 2021-12-11 16:58:49
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 209 ms / 2,000 ms
• コード長: 1,680 bytes
• コンパイル時間: 2,025 ms
• コンパイル使用メモリ: 178,020 KB
• 実行使用メモリ: 16,544 KB
• 最終ジャッジ日時: 2024-11-08 10:15:19
• 合計ジャッジ時間: 4,439 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	5 ms; 6,144 KB
testcase_01	AC	5 ms; 6,016 KB
testcase_02	AC	8 ms; 6,144 KB
testcase_03	AC	6 ms; 6,144 KB
testcase_04	AC	31 ms; 7,424 KB
testcase_05	AC	16 ms; 6,700 KB
testcase_06	AC	17 ms; 6,764 KB
testcase_07	AC	27 ms; 7,168 KB
testcase_08	AC	5 ms; 6,144 KB
testcase_09	AC	33 ms; 8,448 KB
testcase_10	AC	178 ms; 15,428 KB
testcase_11	AC	75 ms; 11,008 KB
testcase_12	AC	23 ms; 7,680 KB
testcase_13	AC	134 ms; 13,340 KB
testcase_14	AC	209 ms; 16,544 KB
testcase_15	AC	50 ms; 6,016 KB
testcase_16	AC	35 ms; 7,552 KB
testcase_17	AC	64 ms; 6,144 KB
testcase_18	AC	5 ms; 6,016 KB

ソースコード

#include <bits/stdc++.h>
#define forn(i,s,t) for(register int i=(s); i<=(t); ++i)
#define form(i,s,t) for(register int i=(s); i>=(t); --i)
#define rep(i,s,t) for(register int i=(s); i<(t); ++i)
using namespace std;
const int N = 1e5 + 4;
bool vis[N]; int p[N], tot;
inline void table(int n = 1e5) {
	forn (i, 2, n) {
		if (!vis[i]) p[++tot] = i;
		for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
			vis[i * p[j]] = 1;
			if (i % p[j] == 0) break ;
		}
	}
}
int n, a[N], b[N], rft[N << 1], fa[N]; map<int, int> Sa, Sb; vector<int> P[N];
int fnd(int u) {return fa[u] == u ? u : fa[u] = fnd(fa[u]); }
inline void mrg(int u, int v) {
	u = fnd(u), v = fnd(v);
	if (u == v) return ;
	fa[v] = u;
}
inline void init() {forn (i, 1, n) P[i].clear(); }
inline void solve() {
	scanf("%d", &n); 
	forn (i, 1, n) scanf("%d", a + i);
	forn (i, 1, n) scanf("%d", b + i);
//	if (a[1] != b[1]) return puts("No"), void();
	forn (i, 1, n) fa[i] = i;
	for (int i = 1; i <= tot && p[i] <= n; ++i) for (int j = p[i] + p[i]; j <= n; j += p[i]) mrg(p[i], j);
	for (int i = 1; i <= tot && p[i] <= n; ++i) {
		int lim = upper_bound(p + 1, p + tot + 1, n / p[i]) - p;
		rep (j, 1, lim) mrg(p[i], p[j]);
	}
	forn (i, 1, n) P[fnd(i)].push_back(i); //printf("%d%c", fnd(i), " \n"[i == n]);
	bool fl = 1;
	forn (i, 1, n) if (i == fnd(i)) {
		Sa.clear(), Sb.clear();
		for (const int& Ps : P[i]) Sa[a[Ps]] ++ , Sb[b[Ps]] ++ ;
		for (const int& Ps : P[i]) {
			if (Sa[a[Ps]] != Sb[a[Ps]]) fl = 0;
//			printf("%d :: %d %d\n", a[Ps], Sa[a[Ps]], Sb[b[Ps]]);
		}
		if (!fl) return puts("No"), void();
	}
	puts("Yes");
}
int Trd;
int main() {
	scanf("%d", &Trd); table();
	while (Trd--) init(), solve();
	return 0;
}