数论模板满足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; }