12tqian's Competitive Programming Library
This documentation is automatically generated by online-judge-tools/verification-helper
verify/codeforces/codeforces-1553G.test.cpp
- View this file on GitHub
- Last update: 2023-01-08 14:16:34-05:00
- Problem: https://codeforces.com/contest/1553/problem/G
Depends on
- library/contest/template-minimal.hpp
- library/graphs/dsu.hpp
- library/misc/fast-hash-map.hpp
- library/misc/fast-input.hpp
- library/number-theory/fast-factor-sieve.hpp
Code
#define PROBLEM "https://codeforces.com/contest/1553/problem/G"
#include "../../library/contest/template-minimal.hpp"
#include "../../library/number-theory/fast-factor-sieve.hpp"
#include "../../library/graphs/dsu.hpp"
#include "../../library/misc/fast-hash-map.hpp"
#include "../../library/misc/fast-input.hpp"
const int N = 1e6 + 5;
const int B = 600;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
Sieve<N> sieve;
int n = read_int();
int q = read_int();
vector<int> a(n);
for (int i = 0; i < n; ++i) {
a[i] = read_int();
}
vector<int> head(N, -1);
DSU dsu;
dsu.init(n);
for (int i = 0; i < n; ++i) {
auto f = sieve.factor(a[i]);
for (auto [p, e] : f) {
if (head[p] == -1) {
head[p] = i;
} else {
dsu.unite(head[p], i);
}
}
}
vector<vector<int>> in(n);
for (int i = 0; i < n; ++i) {
auto f1 = sieve.factor(a[i] + 1);
auto f2 = sieve.factor(a[i]);
reverse(f1.begin(), f1.end());
reverse(f2.begin(), f2.end());
vector<int> f;
while (!f1.empty() || !f2.empty()) {
if (f1.empty()) {
f.push_back(f2.back().first);
f2.pop_back();
} else if (f2.empty()) {
f.push_back(f1.back().first);
f1.pop_back();
} else {
if (f1.back().first == f2.back().first) {
f1.pop_back();
} else if (f1.back().first < f2.back().first) {
f.push_back(f1.back().first);
f1.pop_back();
} else {
f.push_back(f2.back().first);
f2.pop_back();
}
}
}
vector<int> join;
for (int p : f) {
if (head[p] == -1) {
continue;
}
join.push_back(dsu.get(head[p]));
}
sort(join.begin(), join.end());
join.resize(unique(join.begin(), join.end()) - join.begin());
for (int x : join) {
in[x].push_back(i);
}
}
vector<hash_set<int>> check(n);
for (int i = 0; i < n; ++i) {
for (int j : in[i]) {
check[i].insert(j);
}
}
vector<int> ans(q, 2);
vector<bool> big(n);
vector<int> big_sets;
for (int i = 0; i < n; ++i) {
if (in[i].size() >= B) {
big[i] = true;
big_sets.push_back(i);
} else {
big[i] = false;
}
}
vector<vector<int>> table(n);
for (int i : big_sets) {
for (int j : in[i]) {
table[j].push_back(i);
}
}
set<array<int, 2>> good_pairs;
for (vector<int> v : table) {
for (int i : v) {
for (int j : v) {
if (i < j) {
good_pairs.insert({i, j});
}
}
}
}
auto overlap = [&](int u, int v) {
if (u > v) {
swap(u, v);
}
if (big[u] && big[v]) {
if (good_pairs.count({u, v})) {
return true;
} else {
return false;
}
}
if (in[u].size() > in[v].size()) {
swap(u, v);
}
for (int x : in[u]) {
if (check[v].find(x) != check[v].end()) {
return true;
}
}
return false;
};
for (int qq = 0; qq < q; ++qq) {
int s = read_int();
int t = read_int();
--s, --t;
if (dsu.same_set(s, t)) {
ans[qq] = 0;
} else {
int u = dsu.get(s);
int v = dsu.get(t);
if (overlap(u, v)) {
ans[qq] = 1;
} else {
ans[qq] = 2;
}
}
}
for (int qq = 0; qq < q; ++qq) {
cout << ans[qq] << '\n';
}
return 0;
}#define PROBLEM "https://codeforces.com/contest/1553/problem/G"
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
template <int SZ> struct Sieve {
int spf[SZ];
Sieve() {
spf[1] = 1;
for (int i = 2; i < SZ; i++)
spf[i] = i;
for (int i = 4; i < SZ; i += 2)
spf[i] = 2;
for (int i = 3; i * i < SZ; i++)
if (spf[i] == i)
for (int j = i * i; j < SZ; j += i)
if (spf[j] == j)
spf[j] = i;
}
std::vector<std::pair<int, int>> factor(int x) {
std::vector<std::pair<int, int>> ret;
while (x != 1) {
if ((int)ret.size() == 0)
ret.emplace_back(spf[x], 1);
else {
if (ret.back().first == spf[x])
ret.back().second++;
else
ret.emplace_back(spf[x], 1);
}
x /= spf[x];
}
return ret;
}
};
struct DSU {
std::vector<int> e;
DSU() = default;
DSU(int n) { init(n); }
void init(int n) { e = std::vector<int>(n, -1); }
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool same_set(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) return false;
if (e[x] > e[y]) std::swap(x, y);
e[x] += e[y];
e[y] = x;
return true;
}
};
#include <bits/extc++.h>
struct splitmix64_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template <typename K, typename V, typename Hash = splitmix64_hash>
using hash_map = __gnu_pbds::gp_hash_table<K, V, Hash>;
template <typename K, typename Hash = splitmix64_hash>
using hash_set = hash_map<K, __gnu_pbds::null_type, Hash>;
inline char gc() { // like getchar()
static char buf[1 << 16];
static size_t bc, be;
if (bc >= be) {
buf[0] = 0, bc = 0;
be = fread(buf, 1, sizeof(buf), stdin);
}
return buf[bc++]; // returns 0 on EOF
}
int read_int() {
int a, c;
while ((a = gc()) < 40);
if (a == '-') return -read_int();
while ((c = gc()) >= 48) a = a * 10 + c - 480;
return a - 48;
}
const int N = 1e6 + 5;
const int B = 600;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
Sieve<N> sieve;
int n = read_int();
int q = read_int();
vector<int> a(n);
for (int i = 0; i < n; ++i) {
a[i] = read_int();
}
vector<int> head(N, -1);
DSU dsu;
dsu.init(n);
for (int i = 0; i < n; ++i) {
auto f = sieve.factor(a[i]);
for (auto [p, e] : f) {
if (head[p] == -1) {
head[p] = i;
} else {
dsu.unite(head[p], i);
}
}
}
vector<vector<int>> in(n);
for (int i = 0; i < n; ++i) {
auto f1 = sieve.factor(a[i] + 1);
auto f2 = sieve.factor(a[i]);
reverse(f1.begin(), f1.end());
reverse(f2.begin(), f2.end());
vector<int> f;
while (!f1.empty() || !f2.empty()) {
if (f1.empty()) {
f.push_back(f2.back().first);
f2.pop_back();
} else if (f2.empty()) {
f.push_back(f1.back().first);
f1.pop_back();
} else {
if (f1.back().first == f2.back().first) {
f1.pop_back();
} else if (f1.back().first < f2.back().first) {
f.push_back(f1.back().first);
f1.pop_back();
} else {
f.push_back(f2.back().first);
f2.pop_back();
}
}
}
vector<int> join;
for (int p : f) {
if (head[p] == -1) {
continue;
}
join.push_back(dsu.get(head[p]));
}
sort(join.begin(), join.end());
join.resize(unique(join.begin(), join.end()) - join.begin());
for (int x : join) {
in[x].push_back(i);
}
}
vector<hash_set<int>> check(n);
for (int i = 0; i < n; ++i) {
for (int j : in[i]) {
check[i].insert(j);
}
}
vector<int> ans(q, 2);
vector<bool> big(n);
vector<int> big_sets;
for (int i = 0; i < n; ++i) {
if (in[i].size() >= B) {
big[i] = true;
big_sets.push_back(i);
} else {
big[i] = false;
}
}
vector<vector<int>> table(n);
for (int i : big_sets) {
for (int j : in[i]) {
table[j].push_back(i);
}
}
set<array<int, 2>> good_pairs;
for (vector<int> v : table) {
for (int i : v) {
for (int j : v) {
if (i < j) {
good_pairs.insert({i, j});
}
}
}
}
auto overlap = [&](int u, int v) {
if (u > v) {
swap(u, v);
}
if (big[u] && big[v]) {
if (good_pairs.count({u, v})) {
return true;
} else {
return false;
}
}
if (in[u].size() > in[v].size()) {
swap(u, v);
}
for (int x : in[u]) {
if (check[v].find(x) != check[v].end()) {
return true;
}
}
return false;
};
for (int qq = 0; qq < q; ++qq) {
int s = read_int();
int t = read_int();
--s, --t;
if (dsu.same_set(s, t)) {
ans[qq] = 0;
} else {
int u = dsu.get(s);
int v = dsu.get(t);
if (overlap(u, v)) {
ans[qq] = 1;
} else {
ans[qq] = 2;
}
}
}
for (int qq = 0; qq < q; ++qq) {
cout << ans[qq] << '\n';
}
return 0;
}