费马小定理,876. 快速幂求逆元

2023-10-10 06:52

本文主要是介绍费马小定理,876. 快速幂求逆元,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

给定 n 组 ai,pi,其中 pi 是质数,求 ai 模 pi 的乘法逆元,若逆元不存在则输出 impossible

注意:请返回在 0∼p−1 之间的逆元。

乘法逆元的定义

若整数 b,m 互质,并且对于任意的整数 a,如果满足 b|a,则存在一个整数 x,使得 a/b≡a×x(modm),则称 x 为 b 的模 m 乘法逆元,记为 b−1(modm)。

b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时,bm−2 即为 b 的乘法逆元。

输入格式

第一行包含整数 n。

接下来 n 行,每行包含一个数组 ai,pi,数据保证 pi 是质数。

输出格式

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

若 ai 模 pi 的乘法逆元存在,则输出一个整数,表示逆元,否则输出 impossible

数据范围

1≤n≤105,
1≤ai,pi≤2∗109

输入样例:
3
4 3
8 5
6 3
输出样例:
1
2
impossible

 解析:

乘法逆元的定义

若整数 b,m 互质,并且对于任意的整数 a,如果满足 b|a(a能整除b),则存在一个整数 x,使得 a/b≡a×x(modm),则称 x 为 b 的模 m 乘法逆元,记为 b−1(modm)。

b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时,bm−2 即为 b 的乘法逆元。

 更通俗的讲:

给你一个数 b ,找出一个 x ,使得 b*x≡1(mod m)b与m互质

根据定义:
a/b≡a*x(mod m)

我设 b 的逆元为 b^-1

则 a/b≡a*b^-1(mod m)

b*a/b≡a*b^-1*b(mod m)

a≡a*b^-1*b (mod m)

可表示为:b*b^-1≡1 (mod m)

所以逆元类似于乘法中的倒数

费马小定理

b^(p-1)≡1 (mod p)

则 b*b^(p-2)≡1 (mod p)

所以求一个数 b mod p  的逆元,只需要求出 b^(p-2) 即可

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
int a, p;LL quickpow(LL x, LL y, LL mod) {LL t = a, ret = 1;while (y) {if (y & 1)ret = (ret * t) % mod;y >>= 1;t = (t * t) % mod;}return ret;
}int main() {int n;scanf("%d", &n);while (n--) {scanf("%d%d", &a, &p);LL ret = quickpow(a,p-2,p);if (a % p)printf("%lld\n", ret);elseprintf("impossible\n");}return 0;
}

这篇关于费马小定理,876. 快速幂求逆元的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/178750

相关文章

hdu4828(卡特兰数+逆元)

这题的前几个数据分别为1,2,5,14,32......................然后确定这是个卡特兰数列 下面来介绍下卡特兰数,它的递推式为f[i+1] = f[i]*(4*n - 6)/n,其中f[2] = f[3] =1;f[4] = 2;f[5] = 14;f[6] = 32.................................. 但是这题的n太大了,所以要用到逆元,

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

hdu4869(逆元+求组合数)

//输入n,m,n表示翻牌的次数,m表示牌的数目,求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

v0.dev快速开发

探索v0.dev:次世代开发者之利器 今之技艺日新月异,开发者之工具亦随之进步不辍。v0.dev者,新兴之开发者利器也,迅速引起众多开发者之瞩目。本文将引汝探究v0.dev之基本功能与优势,助汝速速上手,提升开发之效率。 何谓v0.dev? v0.dev者,现代化之开发者工具也,旨在简化并加速软件开发之过程。其集多种功能于一体,助开发者高效编写、测试及部署代码。无论汝为前端开发者、后端开发者

利用Django框架快速构建Web应用:从零到上线

随着互联网的发展,Web应用的需求日益增长,而Django作为一个高级的Python Web框架,以其强大的功能和灵活的架构,成为了众多开发者的选择。本文将指导你如何从零开始使用Django框架构建一个简单的Web应用,并将其部署到线上,让世界看到你的作品。 Django简介 Django是由Adrian Holovaty和Simon Willison于2005年开发的一个开源框架,旨在简

CentOs7上Mysql快速迁移脚本

因公司业务需要,对原来在/usr/local/mysql/data目录下的数据迁移到/data/local/mysql/mysqlData。 原因是系统盘太小,只有20G,几下就快满了。 参考过几篇文章,基于大神们的思路,我封装成了.sh脚本。 步骤如下: 1) 先修改好/etc/my.cnf,        ##[mysqld]       ##datadir=/data/loc

SAM2POINT:以zero-shot且快速的方式将任何 3D 视频分割为视频

摘要 我们介绍 SAM2POINT,这是一种采用 Segment Anything Model 2 (SAM 2) 进行零样本和快速 3D 分割的初步探索。 SAM2POINT 将任何 3D 数据解释为一系列多向视频,并利用 SAM 2 进行 3D 空间分割,无需进一步训练或 2D-3D 投影。 我们的框架支持各种提示类型,包括 3D 点、框和掩模,并且可以泛化到不同的场景,例如 3D 对象、室

UE5 半透明阴影 快速解决方案

Step 1: 打开该选项 Step 2: 将半透明材质给到模型后,设置光照的Shadow Resolution Scale,越大,阴影的效果越好