题解 CF571E 【Geometric Progressions】
xht
2020-02-19 00:25:06
> [CF571E Geometric Progressions](https://codeforces.com/contest/571/problem/E)
## 题意
- 给定 $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`。
## 代码
```cpp
#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;
}
```