TLE on test 78 求助

#include <bits/stdc++.h>

using namespace std;

#define int __int128
typedef long long i64;

int mod(int a, int p) {
    if (a<p) return a;
    return a-p*(a/p);
}

#define mul(a,b,p) (mod((a)*(b),p))
constexpr int MAXN=1e2+10;
i64 p; 
mt19937 rnd(time(0));

int qpow(int a, int n, int p) {
    int res=1;
    while (n) {
        if (n&1) res=mul(a,res,p);
        a=mul(a,a,p); n>>=1;
    }
    return res;
}

bool miller_rabin(int a, int x) {
    int d=x-1, r=0;
    while (!(d&1)) d>>=1, ++r;
    int now=qpow(a,d,x); 
    if (now==x-1||now<=1) return true;
    for (int i=1; i<=r; ++i) {
        now=mul(now,now,x);
        if(now==x-1&&i!=r) {
            now=1; break;
        }
        if (now==1) return false;
    }
    return now==1;
}

bool isprime(int x) {
    if (x<3)  return x==2;
    if (x%2==0) return 0;
    for (int i=1; i<=20; ++i)
        if (!miller_rabin(rnd()%(x-1)+1,x)) return false;
    return true;
}


int pollard_rho(int x) {
    int c=mod(rnd(),x-1)+1, s=0, t=0;
    int val=1;
    for (int i=1; ; i<<=1) {
        val=1; s=t;
        for (int step=1; step<=i; ++step) {
            t=mod((mul(t,t,x)+c),x);
            val=mul(val,t-s>0?t-s:s-t,x);
            if (mod(step,127)==0) {
                int d=__gcd(val,x);
                if (d>1) return d;
            }
        }
        int d=__gcd(val,x);
        if (d>1) return d;
    }
    assert(false);
    return -1;
}

int d[MAXN], tot;

void get_fact(int x) {
    if (x<2) return;
    if (isprime(x)) return d[++tot]=x, void();
    int p=x;
    while (p>=x) p=pollard_rho(x);
    get_fact(p); 
    get_fact(x/p);
}

int phip;

int order(int x) {
    if (x==1) return 1;
    int m=phip;
    for (int i=1; i<=tot; ++i) 
        if (qpow(x,m/d[i],p)==1) m/=d[i];
    return m;
}
i64 a, b; 
void solve() {
    cin>>a>>b;
    if (mod(order(a),order(b))==0) cout<<"Yes\n";
    else cout<<"No\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    i64 T; cin>>p>>T;
    get_fact(p); sort(d+1,d+1+tot);
    phip=(d[1]-1)*qpow(d[1],tot-1,1e18);
    tot=0;
    get_fact(phip); sort(d+1,d+1+tot);
    assert(tot<=64);
    while (T--) solve();
}