P11961 的一个无脑做法

Tiat_Siba_Ignareo · 2025-09-30 13:49:16 · 休闲·娱乐

先 O(p^{0.25}) 找到最小原根 g。

然后我们知道，对于所有 x \perp \varphi(p) 的 x，g^x 必定是 p 的一个原根。

所以我们只需要解出方程 g^x \equiv a \pmod p，判断是否有 x \perp \varphi(p) 就做完了。这不是 BSGS 板子吗。

我贺了板子，实际上 \varphi(p)=p-1，都不用写函数求。代码应该是很短的。

以下是我的代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T, n, d, P, qwq, x, y;
map<long, long> mp;
int exgcd(int a, int b, int &x, int &y){
    if (!b){
        x = 1, y = 0;
        return a;
    }
    int g = exgcd(b, a % b, x, y);
    swap(x, y);
    y -= a / b * x;
    return g;
}
int inv(int k, int p){
    exgcd(k, p, x, y);
    return (x % p + p) % p;
}
int qpow(int x, int k, int mod){
    int ans = 1;
    while (k){
        if (k & 1)
            ans = ans * x % mod;
        x = x * x % mod;
        k >>= 1;
    }
    return ans;
}
int bsgs(int a, int b, int p){
    mp.clear();
    int blo = ceil(sqrt(p)), tmp = b;
    for (int i = 0; i <= blo; i++){
        mp[tmp] = i;
        tmp = tmp * a % p;
    }
    int tx = qpow(a, blo, p);
    tmp = 1;
    for (int i = 1; i <= blo; i++){
        tmp = tmp * tx % p;
        if (mp[tmp])
            return i * blo - mp[tmp];
    }
    return -1;
}
int exbsgs(int a, int b, int p){
    //if (p == 1 || (b %= p) == 1)
    //  return 0;
    int g = __gcd(a, p), k = 0, prod = 1;
    while (g > 1){
        if (b % g > 0)
            return -1;
        k++;
        b /= g;
        p /= g;
        prod = prod * (a / g) % p;
        if (prod == b)
            return k;
        g = __gcd(a, p);
    }
    int res = bsgs(a, b * inv(prod, p) % p, p);
    return (res == -1 ? res : res + k);
}
vector<int> ans, di;
int gphi(int x){
    int tx = x, res = x;
    for (int i = 2; i * i <= tx; i++){
        if (tx % i == 0){
            res = res / i * (i - 1);
            while (tx % i == 0)
                tx /= i;
        }
    }
    if (tx > 1)
        res = res / tx * (tx - 1);
    return res;
}
bool pan(int x){
    if (x == 1 || x == 2 || x == 4)
        return 1;
    if (x % 2 == 0)
        x /= 2;
    vector<int> tmp;
    tmp.clear();
    if (x % 2 == 0)
        tmp.emplace_back(2);
    for (int i = 3; i * i <= x; i += 2){
        if (x % i == 0){
            if (tmp.size())
                return 0;
            tmp.emplace_back(i);
            while (x % i == 0)
                x /= i;
        }
    }
    if (x > 1 && tmp.size())
        return 0;
    return 1;
}
void work(int x){
    if (!(x & 1)){
        di.emplace_back(2);
        while (!(x & 1))
            x >>= 1;
    }
    for (int i = 3; i * i <= x; i += 2){
        if (x % i == 0){
            di.emplace_back(i);
            while (x % i == 0)
                x /= i;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> T;
    while (T--){
        cin >> d >> n;
        if (!pan(n)){
            cout << "0\n\n";
            continue;
        }
        P = gphi(n);
        ans.clear();
        di.clear();
        work(P);
        for (int i = 1; i <= n; i++){
            if (__gcd(i, n) != 1)
                continue;
            bool chk = 1;
            for (auto x : di)
                if (qpow(i, P / x, n) == 1){
                    chk = 0;
                    break;
                }
            if (chk){
                qwq = i;
                break;
            }
        }
        int awa = exbsgs(qwq, d, n);
    //  cerr << awa << "\n";
        if (awa == -1 || __gcd(awa, P) != 1)
            cout << "No\n";
        else
            cout << "Yes\n";
    }
    return 0;
}