P5605 小 A 与两位神仙 题解

HappyJaPhy · 2023-12-02 14:39:57 · 题解

• 推销博客
• P5605 小 A 与两位神仙

  题意

• 给定 x、y 和 m，其中 m=p^n,n\in \mathbb{N+},p\ge3，问同余方程 x^a\equiv y\pmod m 是否有非负整数解。

分析

前置芝士

• Pollard_rho
• 原根

化简

• 对这种指数型的同余方程是很难解决的，我们要先把它转化成线性的同余方程。原式很讨人厌的一点就是 x、y 和 a 并不在同一个层次上，但是把 a 降下来很难 （主要是我不会），因此想到将 x 和 y 升到幂的位置上，由此联想到原根。根据原根的存在性判定我们知道 m 存在原根。令 g 为 m 的一个原根，i_x 表示使 g^i\equiv x\bmod m 成立的 i 值，于是有 x^a\equiv y\pmod m

  等价于

  g^{i_xa}\equiv g^{i_y}\pmod m

  等价于

  i_xa\equiv i_y\pmod {\varphi(m)}
• 这是一个线性同余方程，但是我们并不知道 i_x 和 i_y 的值具体为多少，所以这里需要进一步转化。上式等价于 \gcd(i_x,\varphi(m))\mid\gcd(i_y,\varphi(m))

  再由 \large\delta_m(x)=\delta_m(g^{i_x})=\frac{\varphi(m)}{\gcd(i_x,\varphi(m))} 可转化为

  \frac{\varphi(m)}{\delta_m(x)}\mid\frac{\varphi(m)}{\delta_m(y)}

  等价于

  \delta_m(y)\mid\delta_m(x)
• 于是原来的问题就转化为求解 \delta_m(x) 和 \delta_m(y) 了，这就简化很多了，可以直接求解。

求解

• 求欧拉函数很简单，有多种解法，由于这里仅需要 m 这一个数的 \varphi 值，所以直接用 \varphi(p^k)=p^k-p^{k-1} 求解即可。对于 \delta_m(x)，利用 \delta_m(x)\mid\varphi(m) 的性质直接对 \varphi(m) 进行质因数分解，一一试除即可。
• 还有，下面代码用了 (__int128) 的乘法不用会爆 long long，会导致各种错误，我为了这个也就调了 3 个小时而已吧，后面实在不行就照着 Alex_Wei 大佬的代码重改了一遍才发现，血泪教训。
• 还有，求 \varphi(m) 的值我最初是用的 O(\sqrt n) 的单个求法的，交上去 TLE 了之后才意识到会时间爆炸，参考 Alex_Wei 大佬的代码后改用分解质因数的方法（也就是上面说的做法），这种做法的复杂度是 O(n^{\frac{1}4})，快了不少（求完之后记得清空统计质因数的 map，调这玩意花了 30 分钟）。

AC 代码

#include <bits/stdc++.h>
#define int long long
#define inf 1e9
using namespace std;
int n, m, phi, x, y;
map<int, bool> mp;

inline void read(int &x) {
    char ch = x = 0;
    int m = 1;
    while (ch < '0' || ch > '9') {
        ch = getchar();
        if (ch == '-')
            m *= -1;
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + ch - 48;
        ch = getchar();
    }
    x *= m;
    return ;
}

int seed;
inline int rnd(int x) {
    int a = rand() % 1145 + 1;
    x *= a;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    x /= a;
    return abs(x);
}

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

inline int ksmi(__int128 a, int b, int mod) {
    int s = 1;
    while (b) {
        if (b & 1) s = a * s % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return s;
}

inline bool mr(int n) {
    if (n < 3 || n % 2 == 0) return n == 2;
    int r = n - 1, d = 0;
    while ((r & 1) == 0) {
        r >>= 1;
        d++;
    }
    int a, v;
    for (int i = 1; i <= 20; i++) {
        a = seed = rnd(seed);
        a = a % (n - 2) + 2;
        v = ksmi(a, r, n);
        if (v == 1) continue;
        for (int j = 0; j <= d; j++) {
            if (j == d) return 0;
            if (v == n - 1) break;
            v = (__int128)v * v % n;
        }
    }
    return 1;
}

inline int pol(int n) {
    int s = 0, t = 0, now = 1, c = seed = rnd(seed);
    c = c % (n - 1) + 1;
    int k = 1;
    while (1) {
        for (int j = 1; j <= k; j++) {
            t = ((__int128)t * t + c) % n;
            now = (__int128)now * abs(s - t) % n;
            if ((j % 127 == 0 || j == k) && gcd(now, n) > 1) return gcd(now, n);
        }
        s = t;
        k <<= 1;
    }
}

void fac(int n) {
    if (n == 1) return;
    if (mr(n)) {
        mp[n] = 1;
        return ;
    }
    int p = n;
    while (p == n) p = pol(n);
    while (n % p == 0) n /= p;
    fac(p);
    fac(n);
    return ;
}

signed main() {
    srand((unsigned)time(0));
    seed = rand() * rand();
    read(m), read(n);
    fac(m);
    int pri = mp.begin() -> first;
    phi = m - (m / pri);
    mp.clear();
    fac(phi);
    int ordx, ordy, now;
    while (n--) {
        read(x), read(y);
        ordx = ordy = phi;
        for (auto it : mp) {
            now = it.first;
            while (ordx % now == 0 && ksmi(x, ordx / now, m) == 1) ordx /= now;
            while (ordy % now == 0 && ksmi(y, ordy / now, m) == 1) ordy /= now;
        }
        if (ordx % ordy) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}