verify/atcoder/atcoder-abc210_f.test.cpp

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Problem: https://atcoder.jp/contests/abc210/tasks/abc210_f

Depends on

• library/contest/template-minimal.hpp
• library/graphs/two-sat.hpp
• library/number-theory/fast-factor-sieve.hpp

Code

#define PROBLEM "https://atcoder.jp/contests/abc210/tasks/abc210_f"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/graphs/two-sat.hpp"
#include "../../library/number-theory/fast-factor-sieve.hpp"

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	const int V = 2e6 + 5;
	Sieve<V> sieve;
	vector<vector<int>> primes(V);
	int n;
	cin >> n;
	vector<array<int, 2>> v(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 2; ++j) {
			cin >> v[i][j];
			auto f = sieve.factor(v[i][j]);
			for (auto [p, e] : f) {
				primes[p].push_back(j == 0 ? i : ~i);
			}
		}
	}
	TwoSat two_sat;
	two_sat.init(n);
	for (auto& v : primes) {
		two_sat.at_most_one(v);
	}
	auto ans = two_sat.solve();
	if (ans.empty()) {
		cout << "No";
	} else {
		cout << "Yes";
	}
	cout << '\n';
	return 0;
}

#define PROBLEM "https://atcoder.jp/contests/abc210/tasks/abc210_f"


#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;

struct SCC {
	int n, ti;
	
	std::vector<std::vector<int>> g;
	
	std::vector<int> disc, comp, stk, comps;

	void init(int _n) {
		n = _n;
		ti = 0;
		g.resize(n);
		disc.resize(n);
		comp.assign(n, -1);
	}

	void ae(int u, int v) {
		g[u].push_back(v);
	}

	int dfs(int u) {
		int low = disc[u] = ++ti;
		stk.push_back(u);
		for (int v : g[u]) {
			if (comp[v] == -1) {
				low = std::min(low, disc[v] ? : dfs(v));
			}
		}
		if (low == disc[u]) {
			comps.push_back(u);
			for (int v  = -1; v != u; ) {
				comp[v = stk.back()] = u;
				stk.pop_back();
			}
		}
		return low;
	}

	void gen() {
		for (int i = 0; i < n; ++i) {
			if (disc[i] == 0) {
				dfs(i);
			}
		}
		reverse(comps.begin(), comps.end());
	}
};

struct TwoSat {
	int n = 0;
	
	std::vector<std::array<int, 2>> edges;

	void init(int n_) { n = n_; }
	
	int add_var() { return n++; }
	
	void either(int x, int y) {
		x = std::max(2 * x, -1 - 2 * x);
		y = std::max(2 * y, -1 - 2 * y);
		edges.push_back({x, y});
	}

	void implies(int x, int y) { either(~x, y); }
	
	void must(int x) { either(x, x); }
	
	void at_most_one(const std::vector<int>& v) {
		if ((int)v.size() <= 1) {
			return;
		}
		int cur = ~v[0];
		for (int i = 2; i < (int)v.size(); ++i) {
			int nxt = add_var();
			either(cur, ~v[i]);
			either(cur, nxt);
			either(~v[i], nxt);
			cur = ~nxt;
		}
		either(cur, ~v[1]);
	}
	
	std::vector<bool> solve(int n_ = -1) {
		if (n_ != -1) {
			n = n_;
		}
		SCC S;
		S.init(2 * n);
		for (auto [u, v] : edges) {
			S.ae(u ^ 1, v);
			S.ae(v ^ 1, u);
		}
		S.gen();
		reverse(S.comps.begin(), S.comps.end());
		for (int i = 0; i < 2 * n; i += 2) {
			if (S.comp[i] == S.comp[i ^ 1]) {
				return {};
			}
		}
		std::vector<int> tmp(2 * n);
		for (int i : S.comps) {
			if (tmp[i] == 0) {
				tmp[i] = 1;
				tmp[S.comp[i ^ 1]] = -1;
			}
		}
		std::vector<bool> ans(n);
		for (int i = 0; i < n; ++i) {
			ans[i] = tmp[S.comp[2 * i]] == 1;
		}
		return ans;
	}
};

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;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	const int V = 2e6 + 5;
	Sieve<V> sieve;
	vector<vector<int>> primes(V);
	int n;
	cin >> n;
	vector<array<int, 2>> v(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 2; ++j) {
			cin >> v[i][j];
			auto f = sieve.factor(v[i][j]);
			for (auto [p, e] : f) {
				primes[p].push_back(j == 0 ? i : ~i);
			}
		}
	}
	TwoSat two_sat;
	two_sat.init(n);
	for (auto& v : primes) {
		two_sat.at_most_one(v);
	}
	auto ans = two_sat.solve();
	if (ans.empty()) {
		cout << "No";
	} else {
		cout << "Yes";
	}
	cout << '\n';
	return 0;
}

Back to top page