快速幂

二进制分解快速计算幂指数

理论背景

发现 求解 $a^{k}modq$
当k特别大时，算法时间复杂度$O(k)$太大，利用快速幂解决

概念

1. k可以按二进制表示，分解为2的幂相加
2. $a^k$可以用$a^{2^x}$相乘计算
3. $a^{2^x}$可以预处理得到，通过前一个2的幂平方一直得到$2^{lo{g}_{2}k}$次幂
4. 最后累乘可以得到结果
5. 复杂度$O(logn)$

LL qmi(LL a, LL k, LL p)
{
    LL ans = 1;
    while(k)
    {
        if(k & 1)  ans = ans * a % p;  //每次都mod。看k最小位是否为1
        k >>= 1;  // k = k >> 1 去掉最小位
        a = a * a % p;  // 平方,还得mod
    }
    
    return  ans;
}

求逆元

乘法逆元的定义

若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 $a/b\equiv a\times x(modm)$，则称 x 为 b 的模 m 乘法逆元，记为 $b^{-1}(modm)$。

b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，$b^{m-2}$ 即为 b 的乘法逆元。

由费马定理 可得

如果b与m互质，费马定理成立，即$b^{m-1}\equiv 1$ 则 $b\times b^{m-2}=b^{m-1}\equiv 1$

另外，因为同余1，所以m一定大于等于2，m-2一定存在

int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        LL a, p;
        scanf("%lld %lld", &a, &p);
        
        LL res = qmi(a, p - 2, p);  //求a的p-2次幂
        
        if(a % p)  printf("%lld\n", res);  // 因为p是质数，只有这种情况下可能有不互质情况
       else puts("impossible");
    }
    return 0;
}