算法基础-快速幂

(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^8

a = 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;}
}

扩欧求逆元(a和m互质)