题解 CF571E 【Geometric Progressions】

xht · 2020-02-19 00:25:06 · 题解

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 个序列中都有出现的数，或者判断不存在。

题解

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

首先，我们显然要将所有 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;
}