[ACM_其他] Modular Inverse [a关于模m的逆 模线性方程]
Description
The modular modular multiplicative inverse of an integer a modulo m is an integer x such that a-1≡x (mod m)
. This is equivalent toax≡1 (mod m)
.
Input
There are multiple test cases. The first line of input is an integer T ≈ 2000 indicating the number of test cases.
Each test case contains two integers 0 < a ≤ 1000 and 0 < m ≤ 1000.
Output
For each test case, output the smallest positive x. If such x doesn't exist, output "Not Exist".
Sample Input
3
3 11
4 12
5 13
Sample Output
4
Not Exist
8
题目大意:求a关于模m的逆。
解题思路:1>扩展欧几里得算法:找出一对整数对(x,y),使得ax+by=gcd(a,b).
2>设a,b,c为任意整数.若方程ax+by=c的一组整数解为(x,y),则它的任意解为(x+k*b',y+k*a'),其中a'=a/gcd(a,b),b'=b/gcd(a,b),k任意整数.
3>模线性方程:输入正整数:a,b,n,解方程ax≡b(mod n)即:a-b是n的整数倍即:ax-b=ny.
4>ax≡1 (mod m)等价于:ax%m==1%m 也等价于:ax-my=1是否有整数解且求出满足条件的最小整数x。扩展欧几里得算法1必须是gcd(a,m)的倍数,所以a和n互素即:gcd(a,m)=1才会有解,在该条件下有唯一解。
#include<iostream>
#include<string.h>
#include<cstring>
#include<string>
using namespace std;
void gcd(int a,int b,int& d,int& x,int& y){
if(!b){
d=a;x=;y=;
}else{
gcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}//扩展欧几里得算法,a,b,是输入量
//d为gcd(a,b),x,y为ax+by=gcd(a,b)的一组整数解
int main(){
int T;cin>>T;
while(T--){
int a,m,d,x,y;
cin>>a>>m;
gcd(a,m,d,x,y);
if(d!=)cout<<"Not Exist\n";
else{//根据一组解求满足条件的x
if(x>){
while(x>)x-=m;
x+=m;
}else if(x<){
while(x<)x+=m;
}else x+=m;
cout<<x<<'\n';
}
}return ;
}
最新文章
- Android之卫星菜单的实现
- meta标签用法总结
- C# 在异步中使用HttpWebRequest出现的“正在终止线程”错误的解决方案
- 2016 - 1 - 23 json解析
- Android(java)学习笔记208:Android中操作JSON数据(Json和Jsonarray)
- DDD理论学习系列(9)-- 领域事件
- 2 将mybatis配置到springmvc中
- 第三方工具 - 关于echarts下钻功能的一些总结.js
- 771. Jewels and Stones
- Ajax替换局部DIV层
- go标准库的学习-regexp
- 吴裕雄 09-MySQL删除数据表
- 【LOJ】#2114. 「HNOI2015」菜肴制作
- Java并发包中CyclicBarrier的源码分析和使用
- 安装VS提示系统找不到指定路径
- Restful风格wcf调用3——Stream
- asp.net Core2.1连接到Mysql 数据库
- BZOJ4027 HEOI2015兔子与樱花(贪心)
- 集合类---Map
- Android GPS应用(获取定位信息)
热门文章
- UVM Top Testbench
- 关于Eclipse项目中加入jquery.js文件报错(missing semicolon)问题
- htmL5 html5Validate
- windows下安装多个tomcat服务
- textview 多行 省略号
- 开源PLM软件Aras详解三 服务端简易开发
- python profile
- phpcms v9编辑器ckeditor设置回车换行br为段落p标签
- MVC 路由模块内核原理
- Eclipse报错:Setting property &#39;source&#39; to &#39;org.eclipse.jst.jee.server:test1&#39; did no