526互联

AtCoder Beginner Contest 306 G Return to 1

发布时间 2023-06-18 10:47:59作者: zltzlt

洛谷传送门

AtCoder 传送门

考虑若干个能被 \(1\) 到达且能到达 \(1\) 的环，设它们的环长分别为 \(a_1, a_2, ..., a_k\)。

那么我们现在要每个环走若干遍，使得步数不含除 \(2\) 或 \(5\) 以外的质因子。

设第 \(i\) 个环走 \(x_i\) 遍，那么其实就是要求 \(\sum\limits_{i = 1}^k a_i x_i = 10^{10^{100}}\)。

根据裴蜀定理，要求 \(\gcd(a_1, a_2, ..., a_k)\) 不含除 \(2\) 或 \(5\) 以外的质因子。

于是问题转化成求所有环长。

考虑 dfs 树，每一条非树边都对应一个环，找非树边即可。

时间复杂度 \(O(n \log n)\)，瓶颈在求 \(\gcd\)。

加强版是 CF1515G Phoenix and Odometers。

code 
// Problem: G - Return to 1
// Contest: AtCoder - Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306）
// URL: https://atcoder.jp/contests/abc306/tasks/abc306_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200100;

int n, m, d[maxn], g;
bool vis[maxn], mk[maxn];
vector<int> G[maxn], T[maxn];

void dfs(int u) {
	mk[u] = 1;
	for (int v : T[u]) {
		if (!mk[v]) {
			dfs(v);
		}
	}
}

void dfs2(int u) {
	vis[u] = 1;
	for (int v : G[u]) {
		if (!mk[v]) {
			continue;
		}
		if (!vis[v]) {
			d[v] = d[u] + 1;
			dfs2(v);
		} else {
			int t = abs(d[u] + 1 - d[v]);
			g = __gcd(g, t);
		}
	}
}

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		vector<int>().swap(G[i]);
		vector<int>().swap(T[i]);
		d[i] = 0;
		vis[i] = mk[i] = 0;
	}
	while (m--) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].pb(v);
		T[v].pb(u);
	}
	g = 0;
	dfs(1);
	dfs2(1);
	if (!g) {
		puts("No");
		return;
	}
	while (g % 2 == 0) {
		g /= 2;
	}
	while (g % 5 == 0) {
		g /= 5;
	}
	puts(g == 1 ? "Yes" : "No");
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}