#include <bits/stdc++.h>

const int N = 1e6 + 50;
long long x[N], a[N];

int main() {
	long long n;
	std::cin >> n;
	for (int i = 1; i <= n; ++i) {
		std::cin >> x[i] >> a[i];
	}
	std::vector<long long> divisors;
	auto divide = [&](long long x) {
		for (long long i = 1; i * i <= x; ++i)
			if (x % i == 0) {
				divisors.push_back(i);
				if (i != x / i)
					divisors.push_back(x / i);
			}
	};
	for (int i = 1; i <= n; ++i) 
		for (int j = 1; j < i; ++j) 
			if (a[i] != a[j]) {
				long long t = std::abs(x[i] - x[j]);
				divide(t);
			}
	auto check = [&](int d) {
		std::vector<int> s(d, -1);
		int filled = 0;
		for (int i = 1; i <= n; ++i) {
			int y = (x[i] % d + d) % d;
			if (s[y] == -1) {
				s[y] = a[i];
				++filled;
			}
			else if (s[y] != a[i])
				return true;
		}
		if (filled != d) return false;
		for (int t = 1; t < d; ++t) {
			bool ok = true;
			for (int i = 0; i < d; ++i)
				if (s[i] != s[(i + t) % d]) {
					ok = false;
					break;
				}
			if (ok) return true;
		}
		return false;
	};
	for (int d = 1; d <= 50; ++d)
		if (check(d)) {
			divisors.push_back(d);
		}
	std::sort(divisors.begin(), divisors.end());
	divisors.erase(std::unique(divisors.begin(), divisors.end()), divisors.end());
	long long sum = 0;
	for (long long x : divisors)
		sum += x;
	printf("%lld %lld\n", divisors.size(), sum);
}

• 200000 divides 400000, 600000, 800000 and so on
• 3 divides $$$3\cdot 2^k$$$
• 999999000000 is divisible by 999999 and 1000000

#include <bits/stdc++.h>

template<int mod>
struct Z {
	int v;
	Z(long long _v = 0) : v((_v % mod + mod) % mod) {}
	int inc(int x, int y) const { x += y - mod; return x + (x >> 31 & mod); }
	int mul(int x, int y) const { return 1ll * x * y % mod; }
	Z operator+(const Z &rhs) const {
		return Z(inc(v, rhs.v));
	}
	Z operator*(const Z &rhs) const {
		return Z(mul(v, rhs.v));
	}
	bool operator<(const Z &rhs) const {
		return v < rhs.v;
	}
	bool operator==(const Z &rhs) const {
		return v == rhs.v;
	}
	bool operator!=(const Z &rhs) const {
		return v != rhs.v;
	}
};

const int bases[] = { 2333, 19260817, 114514191 };
typedef Z<998244353> Z0;
typedef Z<1000000007> Z1;
typedef Z<1000000009> Z2;
typedef Z<1000000021> Z3;

const int N = 1e6 + 50;

int n, d, f[N];
std::mt19937 s(std::chrono::steady_clock::now().time_since_epoch().count());
std::vector<std::tuple<int, int, int>> edges;
std::vector<std::pair<int, int>> ebuc[N];

struct number {
	Z0 _0;
	Z1 _1;
	Z2 _2;
	Z3 _3;
	number(int v = 0) : _0(v), _1(v), _2(v), _3(v) {}
	number(Z0 _0, Z1 _1, Z2 _2, Z3 _3) : _0(_0), _1(_1), _2(_2), _3(_3) {}
} a[N], a2[N], a3[N], a4[N], a5[N], h[N];

number operator+(const number &x, const number &y) {
	return number(x._0 + y._0, x._1 + y._1, x._2 + y._2, x._3 + y._3);
}
number operator+=(number &x, const number &y) {
	return x = x + y;
}
number operator*(const number &x, const number &y) {
	return number(x._0 * y._0, x._1 * y._1, x._2 * y._2, x._3 * y._3);
}
bool operator<(const number &x, const number &y) {
	if (x._0 != y._0) return x._0 < y._0;
	if (x._1 != y._1) return x._1 < y._1;
	if (x._2 != y._2) return x._2 < y._2;
	return x._3 < y._3;
}
bool operator==(const number &x, const number &y) {
	return x._0 == y._0 && x._1 == y._1 && x._2 == y._2 && x._3 == y._3;
}
bool operator!=(const number &x, const number &y) {
	return x._0 != y._0 || x._1 != y._1 || x._2 != y._2 || x._3 != y._3;
}

int find(int x) {
	while (x != f[x])
		x = f[x] = f[f[x]];
	return x;
}

void merge(int x, int y) {
	x = find(x), y = find(y);
	if (x > y) std::swap(x, y);
	f[x] = y;
}

number getHash(std::vector<int> &b, number *a) {
	number r(0);
	for (int i = 0; i < b.size(); ++i)
		r += a[i] * number(b[i]);
	return r;
}

number getHash(std::vector<number> &b, number *a) {
	number r(0);
	for (int i = 0; i < b.size(); ++i)
		r += a[i] * b[i];
	return r;
}

number pairHash(int u, int v) {
	return number(u) * number(1e6) + number(v);
}

std::map<number, int> map;

void load(number &h) {
	for (int i = 1; i <= n; ++i) f[i] = i;
	std::vector<int> buc;
	for (int i = 1; i < n; ++i) {
		int u, v, w;
		std::cin >> u >> v >> w;
		edges.emplace_back(u, v, w);
		buc.push_back(w);
	}
	auto uni = [&](auto &x) {
		std::sort(x.begin(), x.end());
		x.erase(std::unique(x.begin(), x.end()), x.end());
	};
	uni(buc);
	h = number(2333333) * getHash(buc, a);
	for (auto [u, v, w] : edges) {
		int t = std::lower_bound(buc.begin(), buc.end(), w) - buc.begin();
		ebuc[t].emplace_back(u, v);
	}
	std::vector<number> eigen;
	for (int i = n; i >= 0; --i) 
		if (!ebuc[i].empty()) {
			std::vector<number> set;
			std::vector<int> vertecies;
			std::vector<std::pair<number, int>> vec;
			for (auto [u, v] : ebuc[i]) {
				vertecies.push_back(find(u));
				vertecies.push_back(find(v));
			}
			uni(vertecies);
			for (auto [u, v] : ebuc[i]) merge(u, v);
			for (int y : vertecies)
				vec.emplace_back(find(y), y);
			std::sort(vec.begin(), vec.end());
			std::vector<number> blocks;
			number old = vec[0].first;
			for (auto [fx, x] : vec) {
				if (fx != old) {
					uni(blocks);
					set.emplace_back(getHash(blocks, a2));
					blocks.clear();
					old = fx;
				}
				blocks.emplace_back(x);
			}
			uni(blocks);
			set.emplace_back(getHash(blocks, a3));
			std::sort(set.begin(), set.end());
			eigen.emplace_back(getHash(set, a4));
		}
	h += getHash(eigen, a5);
	edges.clear();
	for (int i = 0; i <= n; ++i) ebuc[i].clear();
}

int ans[N];

int main() {
	for (int i = 0; i < N; ++i) {
		a[i] = number(s()), a2[i] = number(s()), a3[i] = number(s());
		a4[i] = number(s()), a5[i] = number(s());
	}
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::cin >> d >> n;
	std::vector<std::pair<number, int>> vec;
	for (int i = 1; i <= d; ++i) {
		load(h[i]);
		vec.emplace_back(h[i], i);
	}
	std::sort(vec.begin(), vec.end());
	int lst = 0;
	for (int i = 0; i < vec.size(); ++i) {
		if (i == 0 || vec[i].first != vec[i - 1].first) {
			lst = ans[vec[i].second] = vec[i].second;
		}
		else {
			ans[vec[i].second] = lst;
		}
	}
	for (int i = 1; i <= d; ++i) std::cout << ans[i] << " ";
	return 0;
}