学步园

int gcd(int a,int b) {
    while(b) {
        int t=a%b;
        a=b;
        b=t;
    }
    return a;
}
int powmod(int a,int n,int m) {
    if(n==1)return a%m;
    if(n==0)return 1;
    int tmp=powmod(a,n>>1,m)%m;
    tmp=tmp*tmp%m;
    if(n&1)tmp*=a;
    tmp%=m;
    return tmp;
}
int euler(int x) {

    int i, res=x;
    for (i = 2; i < (int)sqrt(x * 1.0) + 1; i++)
        if(x%i==0) {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);
    return res;
}



int main() {
    int x,y;
    int nc;
    scanf("%d",&nc);
    while(nc--) {
        cin>>x>>y;
        if(gcd(x,y)!=1) {
            puts("Not Exist");
            continue;
        }
        printf("%d\n",powmod(x,euler(y)-1,y));
    }
    return 0;
}

求x模y的逆元。如果xy的最大公约数不是0，那么不存在逆元