算法

(阶和原根)

若 $(a, n)=1$，根据欧拉定理有 $a^{\varphi(n)} \equiv 1 \pmod n$，其中 $0 < \varphi(n) < n$ 是 $n$ 缩系的大小。进而，$a^x \equiv 1 \pmod n$ 必有无数正整数解。

根据最小自然数原理，必然可以从其解的集合中取最小的正整数，该数即为 $a^x \equiv 1 \pmod n$ 的阶，称为 $a$ 模 $n$ 的阶，记为 $\delta_n(a)$ 。

换言之， $a$ 模 $n$ 的阶就是 $a^x \equiv 1 \pmod n$ 的最小正整数。

鉴于 $a^0, a^1, \cdots, a^{n-1}$ 均与 $a$ 互质，根据抽屉原理，其中必有两数模 $n$ 同余，进而可以推断出 $1 \leqslant \delta_n(a) \leqslant n-1$。

很自然地我们会问，$\delta_n(n)$ 与 $\varphi(n)$ 什么关系？
$\delta_n(a) \mid \varphi(n)$，即 $a$ 模 $n$ 的阶整除欧拉函数。

若不然，令 $\varphi(n) = \delta_n(a) \times q + r$，可知 $r=0$。

而原根和阶的概念是一一对应的。
满足 $\delta_n(a) = \varphi(n)$ 的 $a$（如果存在）称模 $n$ 的原根。

当 $n$ 为素数时，$\varphi(n) = n-1$
那么，我们只需枚举 $n-1$ 的每个素因子 $p$，验证是否都不满足 $a^{\frac{n-1}{p}} \equiv 1 \pmod n$ 即可。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;
using P = pair<int, int>;

int mod;
//const int mod = 998244353;
//const int mod = 1000000007;
struct mint {
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod) {}
    mint operator-() const {
        return mint(-x);
    }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        return mint(*this) += a;
    }
    mint operator-(const mint a) const {
        return mint(*this) -= a;
    }
    mint operator*(const mint a) const {
        return mint(*this) *= a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return *this *= a.inv();
    }
    mint operator/(const mint a) const {
        return mint(*this) /= a;
    }
};
istream& operator>>(istream& is, mint& a) {
    return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
    return os << a.x;
}

vector<P> factorize(int n) {
    vector<P> res;
    for (int i = 2; i*i <= n; ++i) {
        if (n%i != 0) continue;
        res.emplace_back(i, 0);
        while (n%i == 0) {
            n /= i;
            res.back().second++;
        }
    }
    if (n != 1) res.emplace_back(n, 1);
    return res;
}

bool solve() {
    int a;
    cin >> a >> mod;

    int phi = mod-1;
    auto fs = factorize(phi);
    for (auto [p, _] : fs) {
        if (mint(a).pow(phi/p).x == 1) return false; 
    }
    return true;
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        if (solve()) puts("Yes");
        else puts("No");
    }

    return 0;
}