CF571E Geometric Progressions 题解

CF571E Geometric Progressions

题意

• 给定 $n$ 以及 $n$ 个正整数对 $a_i, b_i$。
• 第 $i$ 对 $a_i, b_i$ 确定了一个序列 $\{a_i, a_i b_i, a_i b_i^2, a_i b_i^3, \ldots \}$。
• 询问最小的在 $n$ 个序列中都有出现的数，或者判断不存在。
• $n \le 100$，$a_i, b_i \le {10}^9$，答案对 ${10}^9 + 7$ 取模。

题解

本题数据范围相对较小，因此保证正确性即可。

首先，我们显然要将所有 $a_i,b_i$ 分解质因数，根号试除即可。

在先处理掉某个 $a_i$ 就是答案的情况之后，设 $P(x)$ 为 $x$ 的质因数集合，若存在 $i,j$ 有 $P(a_i) \cup P(b_i) \ne P(a_j) \cup P(b_j)$，则显然无解。

否则，设 $P = P(a_i) \cup P(b_i)$。

设 $c_i$ 表示最终的答案在第 $i$ 个序列中被表示成 $a_ib_i^{c_i}$，另外设 $c_p(x)$ 表示 $x$ 中质数 $p$ 的次数。

每次考虑合并两个序列 $i,j$，即对于 $p \in P$，需要找到满足 $c_p(a_i) + c_i \cdot c_p(b_i) = c_p(a_j) + c_j \cdot c_p(b_j)$ 的 $c_i$ 的取值。

那么对于每个 $p \in P$，我们都能列出一个这样的方程。

解这个方程组，结果要么判断出无解，要么直接确定 $c_i$ 的值，要么要解一个不定方程。

前面两种情况都很好处理。对于最后一种情况，可以用扩展欧几里得求出最小非负整数解，若设为 $x$，则合并后的新序列中，$a^{\prime} = a_i \cdot b_i^x$，$b^{\prime} = \sum_{p} p^{\operatorname{lcm}(c_p(b_i), c_p(b_j))}$。

合并到最后，$a^{\prime}$ 即为答案。

整个过程中，涉及到的数肯定会很大，因此直接把每个数用其唯一分解式存就行了。

注意，指数会爆 int 但不会爆 long long。

代码

#define Fail print(-1), exit(0)
const int N = 107;
int n;
struct Num {
	vector<pair<int, ll>> p;
	inline void in() {
		int x;
		rd(x);
		for (int i = 2; i * i <= x; i++)
			if (!(x % i)) {
				p.pb(mp(i, 0ll));
				while (!(x % i)) ++p.back().se, x /= i;
			}
		if (x != 1) p.pb(mp(x, 1ll));
	}
	inline void out() {
		modint ans = 1;
		for (auto o : p) ans *= (modint)o.fi ^ o.se;
		print(ans);
	}
	#define s(o) o.p.size()
	#define x(o) x.p[o]
	#define y(o) y.p[o]
	#define z(o) z.p.pb(o)
	inline friend Num operator * (Num x, Num y) {
		Num z;
		ui i = 0, j = 0;
		while (i < s(x) && j < s(y))
			if (x(i).fi == y(j).fi)
				z(mp(x(i).fi, x(i).se + y(j).se)), ++i, ++j;
			else if (x(i).fi < y(j).fi) z(x.p[i++]);
			else z(y.p[j++]);
		while (i < s(x)) z(x.p[i++]);
		while (j < s(y)) z(y.p[j++]);
		return z;
	}
	inline friend bool operator % (Num x, Num y) {
		for (ui i = 0, j = 0; j < s(y); i++, j++) {
			while (i < s(x) && x(i).fi != y(j).fi) ++i;
			if (i == s(x) || x(i).se < y(j).se) return 1;
		}
		return 0;
	}
	inline friend Num operator / (Num x, Num y) {
		Num z;
		for (ui i = 0, j = 0; i < s(x); i++)
			if (j < s(y) && x(i).fi == y(j).fi) {
				z(mp(x(i).fi, x(i).se - y(j++).se));
				if (!z.p.back().se) z.p.pop_back();
			} else z(x(i));
		return z;
	}
	inline friend Num operator & (Num x, Num y) {
		Num z;
		for (ui i = 0, j = 0; i < s(x); i++)
			if (j < s(y) && x(i).fi == y(j).fi)
				z(mp(x(i).fi, x(i).se - y(j++).se));
			else z(x(i));
		return z;
	}
	inline friend bool operator | (Num x, Num y) {
		if (!s(x)) return 0;
		ll k;
		for (ui i = 0, j = 0; i <= s(x); i++, j++) {
			while (j < s(y) && !y(j).se) ++j;
			if (i == s(x)) {
				if (j == s(y)) return 0;
				return 1;
			}
			if (j == s(y)) return 1;
			if (x(i).fi != y(j).fi || x(i).se % y(j).se) return 1;
			if (!i) k = x(i).se / y(j).se;
			else if ((x(i).se / y(j).se) != k) return 1;
		}
		return 0;
	}
	inline friend Num operator ^ (Num x, ll y) {
		for (auto &o : x.p) o.se *= y;
		return x;
	}
	inline friend Num operator + (Num x, Num y) {
		Num z;
		for (ui i = 0; i < s(x); i++)
			z(mp(x(i).fi, x(i).se * y(i).se / __gcd(x(i).se, y(i).se)));
		return z;
	}
} a[N], b[N], c[N], A, B;

inline bool pd(Num x) {
	for (int i = 1; i <= n; i++)
		if ((x % a[i]) || ((x / a[i]) | b[i])) return 0;
	return 1;
}

struct Pro {
	ll k, b, p;
	inline Pro() {}
	inline Pro(ll k, ll b, ll p) : k(k), b(b), p(p) {}
	inline bool operator == (const Pro o) const {
		return k == o.k && b == o.b && p == o.p;
	}
};

inline ll solve(Pro x, Pro y) {
	ll a = x.b * y.p - y.b * x.p, b = x.k * y.p - y.k * x.p;
	if (!b || a % b) Fail;
	return a / b;
}

ll exgcd(ll a, ll b, ll &x, ll &y, ll d = 0ll) {
	return b ? (d = exgcd(b, a % b, y, x), y -= a / b * x, d) : (x = 1, y = 0, a);
}

inline bool merge(int o) {
	vector<Pro> pro;
	for (ui i = 0; i < A.p.size(); i++) {
		ll k1 = B.p[i].se, b1 = A.p[i].se;
		ll k2 = b[o].p[i].se, b2 = a[o].p[i].se;
		if (!k1 && !k2) {
			if (b1 != b2) Fail;
			continue;
		}
		if (!k1) {
			if (b1 < b2 || (b1 - b2) % k2) Fail;
			A = a[o] * (b[o] ^ ((b1 - b2) / k2));
			return 0;
		}
		if (!k2) {
			if (b2 < b1 || (b2 - b1) % k1) Fail;
			A = A * (B ^ ((b2 - b1) / k1));
			return 0;
		}
		ll d = __gcd(k1, k2), g = b2 - b1;
		if (g % d) Fail;
		g /= d, k1 /= d, k2 /= d;
		if (pro.size()) {
			if (pro[0] == Pro(k1, g, k2)) continue;
			A = A * (B ^ solve(pro[0], Pro(k1, g, k2)));
			return 0;
		}
		pro.pb(Pro(k1, g, k2));
	}
	if (pro.size()) {
		ll k = pro[0].k, b = pro[0].b, p = pro[0].p, x, y;
		b = (b % p + p) % p;
		exgcd(k, p, x, y);
		x = (x * b % p + p) % p;
		A = A * (B ^ x);
		B = B + ::b[o];
	}
	return 1;
}

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) a[i].in(), b[i].in(), c[i] = a[i] * b[i];
	for (int i = 1; i <= n; i++) if (pd(a[i])) return a[i].out(), 0;
	for (int i = 1; i <= n; i++) {
		if (c[i].p.size() != c[1].p.size()) Fail;
		for (ui j = 0; j < c[1].p.size(); j++)
			if (c[i].p[j].fi != c[1].p[j].fi) Fail;
		a[i] = c[i] & b[i], b[i] = c[i] & a[i];
	}
	A = a[1], B = b[1];
	for (int i = 2; i <= n; i++)
		if (!merge(i)) {
			if (pd(A)) return A.out(), 0;
			Fail;
		}
	A.out();
	return 0;
}