首页 > 其他分享 >快速幂已经快速幂求逆元(数论)

快速幂已经快速幂求逆元(数论)

时间:2024-10-23 20:50:01浏览次数:5  
标签:幂求 ai res ll int 逆元 pi 快速

快速幂模板

给定 n 组 ai,bi,pi对于每组数据,求出 ai ^ bi mod pi 的值。

输入格式

第一行包含整数 n。

接下来 n 行,每行包含三个整数 ai,bi,pi。

输出格式

对于每组数据,输出一个结果,表示 ai ^ bi mod pi 的值。

每个结果占一行。

数据范围

1≤n≤100000
1≤ai,bi,pi≤2×10^9

输入样例:

2
3 2 5
4 3 9

输出样例:

4
1

代码

 

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;


LL qmi(int a, int b, int p)
{
    LL res = 1 % p;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * (LL)a % p;
        b >>= 1;
    }
    return res;
}


int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        printf("%lld\n", qmi(a, b, p));
    }

    return 0;
}


快速幂求逆元

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

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

乘法逆元的定义

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

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

输入格式

第一行包含整数 n。

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

输出格式

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

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

数据范围

1≤n≤10^5
1≤ai,pi≤2∗10^9

输入样例:

3
4 3
8 5
6 3

输出样例:

1
2
impossible

逆元

在取模操作中,逆元是指在模 n 的情况下,对于一个整数 a(且 a 和 n 互质),存在一个整数 b,使得 a ⋅ b ≡ 1 mod  n。这个 b 被称为 a 的模逆元。求模逆元通常可以使用扩展欧几里得算法。 

假设我们要计算 3 / 5 mod 7那么就是要计算5的逆元

费马小定理

 

代码

#include <iostream>

using namespace std;

typedef long long ll;

int t;
ll a,p;

ll qmi(ll m, ll k, ll p)
{
    ll res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}
 
ll inv(ll a,ll p)
{
    return qmi(a,p - 2,p);
} 

void solve()
{
    cin >> a >> p;
    if(a % p == 0) cout << "impossible" << endl;
    else cout << inv(a,p) << endl;
}

int main()
{
    cin >> t;
    while(t --){
        solve();
    }
    return 0;
}

加油

标签:幂求,ai,res,ll,int,逆元,pi,快速
From: https://blog.csdn.net/AuRoRamth/article/details/143193289

相关文章

  • 使用 Cursor 和 Devbox 快速开发并上线 Gin 项目
    作为开发者,最让我们头疼的事情是什么?那必须是环境配置、版本控制以及各种部署配置等等繁琐的工作。想象一下,如果你只需点击几下鼠标,就能拥有一个完全配置好的开发环境,支持从Java到Python,从React到Vue的各种主流技术栈。而且可以自动分配域名、HTTPS证书,免去繁琐的配置流......
  • 快速变现!AI插画月入5W不是梦!
    ​在这个数字化飞速发展的时代,你是否也想利用AI技术,实现财富自由?今天给大家拆解1个变现方式,即创作治愈系插画。—AIGC绘画创作无限—●想知道治愈系账号是如何吸引上万粉丝的吗?答:在这个快节奏、高压力的时代,烦躁、失眠、焦虑、内耗和孤独感仿佛成了当代中青年人难以......
  • 使用qgis.core模块快速转换s57数据
    importosfromqgis.coreimport(QgsVectorLayer,QgsVectorFileWriter)#解析S57图层信息的函数defextract_s57_layer_info(s57layers:list[str])->list[tuple]:extracted_info=[]#内部的解析函数defparse_layer_info(layer_info)......
  • LTE 利用FFT 实现PSS的快速相关
    本期介绍一下怎么利用快速傅里叶变换来实现LTEPSS的快速相关。看下数字信号处理书本上线性卷积的数学表达式:假设h(n)和x(n)的长度分别为N和M,线性卷积的结果用yline(n)表示,则对比一下可以发现LTEPSS相关可以用线性卷积来实现,只需要把本地序列共轭翻转。我们知道用FFT方......
  • LTE 基于快速哈达玛hadamard变换SSS辅同步信号SSS检测之hadamard变换公式推导
    LTESSSs序列生成的阶数为31阶,所以hadamard矩阵的阶数为32阶,定义一个32阶的hadamard矩阵H32,下面进行hadamard快速变换公式推导继续分解后面公式的推导小编还在继续......
  • Python的京东探险记:揭秘商品详情的快速通道
    在一个充满无限可能的数字世界里,Python,这位编程界的多面手,正准备踏上一场刺激的探险之旅:快速获取京东商品的详情数据。这不仅是一次技术的挑战,更是一次与时间赛跑的较量。!Python先生,这位机智的代码探险家,打开了他的笔记本电脑,准备开始这场冒险。他知道,要快速获取京东的商品详情......
  • 对象存储服务MinIO-快速入门-集成项目
    对象存储服务MinIOMinIO简介MinIO基于ApacheLicensev2.0开源协议的对象存储服务,可以做为云存储的解决方案用来保存海量的图片,视频,文档。由于采用Golang实现,服务端可以工作在Windows,Linux,OSX和FreeBSD上。配置简单,基本是复制可执行程序,单行命令可以运行起来。MinIO......
  • SpringBoot-集成腾讯云对象存储Cos-快速入门
    腾讯云对象存储COS一准备工作1注册腾讯云首先注册与登录等腾讯云,官网地址:https://cloud.tencent.com/2开通腾讯云对象存储COS腾讯云对象存储COS:官网地址:https://cloud.tencent.com/product/cos3进入控制台创建存储桶填写信息第二页直接默认就好这里的请求......
  • 快速排序
    一、快速排序的介绍快速排序简单来说就是指先选择一个基准元素(默认第一个是基准元素),再去找到比基准元素大的元素,放在基准元素的右边,比基准元素小的放在基准元素的左边,再将找到的最后一个比基准元素小的元素与基准元素进行交换动画演示的网址https://visualgo.net/en/sorting......
  • Docker快速使用
    Docker快速使用镜像操作检索:dockersearch搜索nginx:$dockersearchnginxNAMEDESCRIPTIONSTARSOFFICIALnginxOfficialbuildofNginx.......