侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【快速幂】快速幂求逆元

GabrielxD
2023-03-05 / 0 评论 / 3 点赞 / 405 阅读 / 1,061 字
温馨提示:
本文最后更新于 2023-03-22,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

876. 快速幂求逆元 - AcWing题库


给定 nnai,pia_i, p_i ,其中 pip_i 是质数,求 aia_ipip_i 的乘法逆元,若逆元不存在则输出 impossible

注意:请返回在 0p10 \sim p-1 之间的逆元。

乘法逆元的定义

若整数 bmb,m 互质,并且对于任意的整数 aa ,如果满足 bab|a ,则存在一个整数 xx ,使得 a/ba×x(modm)a/b≡a \times x \pmod m ,则称 xxbb 的模 mm 乘法逆元,记为 b1(modm)b^{-1} \pmod m
bb 存在乘法逆元的充要条件是 bb 与模数 mm 互质。当模数 mm 为质数时, bm2b^{m-2} 即为 bb 的乘法逆元。

输入格式

第一行包含整数 nn

接下来 nn 行,每行包含一个数组 ai,pia_i, p_i ,数据保证 pip_i 是质数。

输出格式

输出共 nn 行,每组数据输出一个结果,每个结果占一行。

aia_ipip_i 的乘法逆元存在,则输出一个整数,表示逆元,否则输出 impossible

数据范围

1n1051 \le n \le 10^5 ,
1ai,pi21091 \le a_i,p_i \le 2*10^9

输入样例:

3
4 3
8 5
6 3

输出样例:

1
2
impossible

解题

方法一:快速幂

逆元

定义

若整数 b,pb, p 互质[1],且对于任意一个整数 aa ,如果满足 bab \mid a [2] ,则存在一个整数 xx ,使得 abax(modp)\frac{a}{b} \equiv a \cdot x \pmod p [3] 。称 xxbb 在模 pp 意义下的乘法逆元,记作 b1(modp)b^{-1} \pmod p

作用

在要除以一个数,再取模时,把除法变成乘法运算,然后再取模

思路

根据逆元的定义,有: abab1(modp)\frac{a}{b} \equiv a \cdot b^{-1} \pmod p

两边同乘 bb 得: aabb1(modp)a \equiv a \cdot b \cdot b^{-1} \pmod p

所以: bb11(modp)b \cdot b^{-1} \equiv 1 \pmod p ①;

根据费马小定理 :若 pp 为质数且 b,pb, p 互质,则 bp11(modp)b^{p-1} \equiv 1 \pmod p

从上式 bp1b^{p-1} 中拆出一个 bb 得到: bbp21(modp)b \cdot b^{p-2} \equiv 1 \pmod p

结合①式得到:b1bp2(modp)b^{-1} \equiv b^{p-2} \pmod p

综上,在 bb 存在乘法逆元的条件下,求出 bp2modpb^{p-2} \bmod p 即为 bb 在模 pp 意义下的乘法逆元

使用快速幂求解即可。

注意:题目虽然保证 pp 为质数,但是并没有保证 b,pb, p 互质,所以在算之前要判断逆元是否存在。

代码

import java.util.*;
import java.io.*;

public class Main {
    static long quickPow(long base, long exp, long mod) {
        long res = 1L;
        while (exp > 0) {
            if ((exp & 1) == 1) res = res * base % mod;
            base = base * base % mod;
            exp >>= 1;
        }
        return res;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        while (n-- > 0) {
            in.nextToken();
            int a = (int) in.nval;
            in.nextToken();
            int p = (int) in.nval;
            System.out.println(a % p == 0 ? "impossible" : quickPow(a, p - 2, p));
        }
    }
}

  1. gcd(b,m)=1\gcd(b, m) = 1↩︎

  2. aa 能被 bb 整除( ab\frac{a}{b} 是一个整数 )。 ↩︎

  3. ab\frac{a}{b} 在模 pp同余于 axa \cdot xabmodp=axmodp\frac{a}{b} \bmod p = a \cdot x \bmod p )。 ↩︎

3

评论区