(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
(a ^ b) % p = ((a % p)^b) % p
快速幂
3^10
10 = 1010 = 2^2 + 2^3
3^10 = 3 * 2^2 + 3 * 2^3 = 3^4 + 3^8a = a * a => a a^2 a^4 a^8
所以当 b & 1 == 1 时, res = res *a;
long long qmi(long long a,int b,int p)
{long long res=1;while(b){if(b&1) res = res *a %p;b>>=1;//更新a,a依次为a^{2^0},a^{2^1},a^{2^2},....,a^{2^logb}a=a*a%p;}return res;
}
快速幂求逆元
求某个数的逆元,实际上就是求一个数x,使得(a * x) % p == 1
即原本的 a%p != 1,使得:ax % p == 1
当b、m互质时,b 的倍数 a 在模m情况下也有相应逆元,否则不存在
public class Main {public static void main(String[] args) throws Exception {Scanner in = new Scanner(System.in);int n = in.nextInt();for(int i = 0; i < n; i ++) {long a = in.nextLong();long p = in.nextLong();long res = quick(a, p - 2,p);if(a % p == 0)System.out.println("impossible");elseSystem.out.println(res);}}private static long quick(long a, long b, long p) {long res = 1;while(b != 0) {if(b % 2 == 1)res = res * a % p;b = b >> 1;a = a * a % p;}return res;}
}