Luogu P5605 小A与两位神仙

题目描述

https://www.luogu.com.cn/problem/P5605

简要题意：给定一个整数 $n$，保证 $n$ 是奇质数 $p$ 的正整数次方，现在有 $m$ 次询问，每次询问给定两个正整数 $x,y$，保证 $(x,n)=1,(y,n)=1$，问是否存在非负整数 $a$，使得 $x^a\equiv y(\bmod n)$

$x,y<n\le 10^{18},m\le 2\times 10^4$

Solution

因为保证 $n$ 是奇质数的正整数次方，所以 $n$ 一定存在原根 $g$ 和非负整数 $s,t$，使得 $x\equiv g^s(\bmod n),y\equiv g^t(\bmod n)$，那么询问变为是否存在非负整数 $a$，使得 $sa\equiv t(\bmod \varphi(n))$，该式有解当且仅当 $(s,\varphi(n))|t$，即 $(s,\varphi(n))|(t,\varphi(n))$

根据阶的性质，我们有 $\delta_n(g^k)=\frac{\delta_n(g)}{(\delta_n(g),k)}$，所以如果存在非负整数 $a$，则一定有 $\delta_n(y)|\delta_n(x)$，至于如何验证这个东西，我们一定有 $\delta_n(y)|\varphi(n)$，所以我们考虑对于首先对于 $\varphi(n)$ 分解质因数，然后通过不断试除来得到 $\delta_n(x)$，然后通过验证 $y^{\delta_n(x)}$ 是否同余 $1$ 即可

时间复杂度 $O(nm^{\frac{1}{4}})$

#include <iostream>
#include <numeric>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

inline ll mul(ll x, ll y, ll p) { return (x * y - (ll) ((long double) x / p * y) * p + p) % p; }
ll pow_mod(ll x, ll n, ll p) {
    ll s = 1;
    for (; n; n >>= 1, x = mul(x, x, p))
        if (n & 1) s = mul(s, x, p);
    return s;
}

bool isp(ll n) {
    if (n == 1 || n % 6 % 4 != 1) return (n | 1) == 3;
    ll k = __builtin_ctzll(n - 1), m = n >> k;
    for (ll t : { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 }) {
        ll p = pow_mod(t % n, m, n), i = k;
        while (p != 1 && p != n - 1 && t % n && i--) p = mul(p, p, n);
        if (p != n - 1 && i != k) return false;
    } return true;
}
ll rho(ll n) {
    auto f = [&](ll x) { return mul(x, x, n) + 1; };
    ll p = 2, q;
    for (ll i = 1, x = 0, y = 0, t = 30; t++ % 40 || gcd(p, n) == 1; x = f(x), y = f(f(y))) {
        if (x == y) x = ++i, y = f(x);
        q = mul(p, x < y ? y - x : x - y, n);
        if (q) p = q;
    } return gcd(p, n);
}
vector<ll> factorilize(ll n) {
    if (n == 1) return {};
    if (isp(n)) return {n};
    ll t = rho(n);
    auto l = factorilize(t), r = factorilize(n / t);
    l.insert(l.end(), r.begin(), r.end());
    return l; 
}

ll n;
int m; 

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    ll phi = n - n / factorilize(n)[0]; vector<ll> vec = factorilize(phi);
    sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end());
    for (int i = 1; i <= m; ++i) {
        ll x, y, res = phi; cin >> x >> y;
        for (auto p : vec) 
            while (res % p == 0 && pow_mod(x, res / p, n) == 1) res /= p;
        cout << (pow_mod(y, res, n) == 1 ? "Yes" : "No") << "\n";
    }
    return 0; 
}