数论模板 满足a^x≡1(mod n)的最小正整数

Description

满足a^x≡1(mod n)的最小正整数x称为a模n的阶。

现给出两个正整数，求x。

Input

第一行输入k，表示有k组数据

之后k行每行两个数a,n(2<=a,n<=10^9)

Output

对于每组输入，用一行输出x的值，若不存在输出-1

Sample Input

22 32 4

Sample Output

2-1

Hint

当a与n不互质的时候，肯定不存在，否则x的最大值是x的欧拉函数，所以要从x的欧拉函数的因子中筛，考虑此题的数据范围，欧拉函数直接求，gcd用二进制，

满足a^x≡1(mod n)的最小正整数x称为a模n的阶。

现给出两个正整数，求x。

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <climits>
#include <cmath>
using namespace std;
#define SIZE 655
//筛法求欧拉函数
int Euler[SIZE] = {0};
void sieve(){
    Euler[1] = 1;
    for(int i=2;i<SIZE;++i){
        if ( Euler[i] ) continue;

        for(int j=i;j<SIZE;j+=i){
            if ( !Euler[j] ) Euler[j] = j;

            Euler[j] = Euler[j] / i * ( i - 1 );
        }
    }
}
typedef int int_t;
int_t gcd(int_t a,int_t b){
    while( b ){
        int_t r = b;
        b = a % b;
        a = r;
    }
    return a;
}
//快速GCD
int Fastgcd(int a, int b)
{
    if (a == 0) return b;
    if (b == 0) return a;
    if (!(a & 1) && !(b & 1))
        return Fastgcd(a>>1, b>>1)<<1;
    else if (!(b & 1))
    return Fastgcd(a, b>>1);
    else if (!(a & 1)) return Fastgcd(a>>1, b);
    else return Fastgcd(abs(a - b), min(a, b));
}
int euler_phi(int n)
{
    int m = floor(sqrt(n+0.5));
    int ans = n;
    for(int i = 2; i <= m; i++) if(n%i == 0)
    {
        ans = ans / i * (i-1);
        while(n%i == 0)
        {
            n /= i;
        }
    }
    if(n > 1) ans = ans / n *(n-1);
    return ans;
}
//计算a^b%mod
typedef long long llt;
llt powerMod(llt a,llt b,llt mod){
    llt ret = 1LL;
    a %= mod;
    while( b ){
        if ( b & 1LL ) ret = ret*a % mod,--b;//multiMod(ret,a,mod),--b;
        b >>= 1LL;
        a = a*a%mod;//multiMod(a,a,mod);
    }
    return ret;
}

int main(){
    //sieve();
    int k;scanf("%d",&k);
    while(k--){
        int a,n;
        scanf("%d%d",&a,&n);
        if ( Fastgcd(a,n) == 1){
            //printf("%d\n",Euler[n]);
            int tmp = euler_phi(n);
            int ans = INT_MAX;
            for (int i = 1;i*i <= tmp;++i){
                if ( tmp % i  ) continue;
                if (1 == powerMod( a,i,n) ) ans = min(ans,i);
                if (1 == powerMod( a,tmp/i,n)) ans = min(ans,tmp/i);
            }
            printf("%d\n",ans);
        }
        else
            printf("-1\n");
    }
    return 0;
}