博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hiho1530(扩展欧几里得求模逆元)
阅读量:6704 次
发布时间:2019-06-25

本文共 1354 字,大约阅读时间需要 4 分钟。

#1530 : 分数取模

时间限制:
1000ms
单点时限:
10000ms
内存限制:
256MB

描述

给定三个正整数 abp,满足 bp 互质。这时分数 a / b 除以 p 的余数,即 a / b MOD p 可以定义为 a × b-1 MOD p。  

其中b-1b 的逆元,它满足 1 ≤ b-1 < pb × b-1 ≡ 1 MOD p,满足上述条件的 b-1有且仅有一个。  

例如 2-1 ≡ 4 MOD 7,因为2 × 4 ≡ 1 MOD 7; 3-1 ≡ 3 MOD 8,因为3 × 3 ≡ 1 MOD 8。  

于是我们可以利用b-1求出a / b MOD p,例如: 3 / 2 MOD 7 = 3 × 2-1 MOD 7 = 3 × 4 MOD 7 = 5

给定三个正整数 abp,满足 bp 互质,求 a / b MOD p。  

输入

第一行包含3个正整数,abp 满足 bp 互质。  

对于30%的数据,1 ≤ a, b < p ≤ 100

对于80%的数据,1 ≤ a, b < p ≤ 100000  

对于100%的数据,1 ≤ a, b < p ≤ 1000001333

输出

输出 a / b MOD p的值。

样例输入
3 2 7
样例输出
5 分析:a/b MOD p的意思就是(a*b-1)MOD p,这里b-1指的是b关于p的乘法逆元,令x=b-1, 即b*x MOD p=1 ==> b*x=p*y+1 ==> bx+(-py)=1=gcd(b,p),然后用扩展gcd求特解x。 注意:这里b与p互质 摘自维基百科:

模逆元也称为模倒数,或者模逆元

一a对n之模逆元是指满足以下公式的整数 b

a^{​{-1}}\equiv b{\pmod  {n}}.

也可以写成以下的式子

ab\equiv 1{\pmod  {n}}.

整数 a 对模数 n 之模逆元存在的是 a 和 n ,若此模逆元存在,在模数 n 下的除法可以用和对应模逆元的乘法来达成,此概念和实数除法的概念相同。

下面给出扩展gcd求模逆元的代码
#include
long long exgcd(long long a,long long b,long long &x,long long &y){
//求出gcd(a,b)顺带求出一组特解使得ax+by=gcd(a,b) if(b==0) { x=1; y=0; return a; } int r=exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return r;}int main(){ long long a,b,p,x,y; scanf("%lld%lld%lld",&a,&b,&p); long long r=exgcd(b,p,x,y); printf("%lld\n",a*((x+p)%p)%p); return 0;}
View Code

 

 

转载于:https://www.cnblogs.com/ACRykl/p/8729252.html

你可能感兴趣的文章
游戏安全资讯精选 2017年 第七期:游戏账号窃取日益猖獗,Struts2 REST插件远程执行命令漏洞全面分析,2017世界物联网博览会IoT安全观点...
查看>>
项立刚:FDD牌照发放 难改行业大格局
查看>>
移动广告作弊流量超过30%?你中招了吗
查看>>
CentOS 6.5环境 MongoDB 3.2.8 单实例安装部署
查看>>
基于阿里云MaxCompute实现复杂事件检测
查看>>
一键部署自动感知服务的Docker集群(一)
查看>>
【D3.js 学习总结】17、D3布局-分区图(矩形)
查看>>
《C语言及程序设计》实践项目——数组与指针
查看>>
MySQL中char和varchar有啥区别?优缺点是啥?
查看>>
PostgreSQL的函数安全定义解说
查看>>
pageinspect介绍
查看>>
C++语言基础 例程 类声明和成员函数定义的分离
查看>>
剑指offer学习笔记2
查看>>
面向对象
查看>>
动态分配的顺序线性表的十五种操作—C语言实现
查看>>
解决海量数据计算、降低企业成本的利器——MaxCompute
查看>>
JPEG编码
查看>>
github push403错误的处理
查看>>
正确理解ThreadLocal
查看>>
C# 文件流压缩解压
查看>>