51Nod 1256 扩展欧几里得求乘法逆元
2024-08-25 22:55:13
给出2个数M和N(M < N),且M与N互质,找出一个数K满足0 < K < N且K * M % N = 1,如果有多个满足条件的,输出最小的。
Input
输入2个数M, N中间用空格分隔(1 <= M < N <= 10^9)
Output
输出一个数K,满足0 < K < N且K * M % N = 1,如果有多个满足条件的,输出最小的。
Sample Input
2 3
Sample Output
2
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<deque>
#include<iostream>
using namespace std;
typedef long long LL;
void ex_gcd(LL a,LL b,LL &x,LL &y,LL &d)
{
if(!b) {x = ,y = ,d = a;}
else
{
ex_gcd(b,a%b,y,x,d);
y -= x * (a / b);
}
}
LL inv(LL a,LL b)
{
LL x,y,d;
ex_gcd(a,b,x,y,d);
return d == ?((x % b) + b)%b : -;
}
int main()
{
LL n,m;
int i,p,j;
scanf("%lld%lld",&m,&n);
printf("%lld\n",inv(m,n));
return ;
}
最新文章
- 第二天-uboot学习
- 数据结构之二分查找(PHP)
- 【入门】匈牙利算法+HNOI2006 hero超级英雄
- 【BZOJ-3651&;3081】网络通信&;StrangeRegulations Link-Cut-Tree
- 6.python字符串-内置方法列举
- warning:performSelector may cause a leak because its selector
- JavaScript(class0526)
- sed线上经典案例之-同时替换多个字符串
- w3school教程整理
- codeforces 55D. Beautiful numbers 数位dp
- [Usaco2008 Jan]Cow Contest奶牛的比赛[神奇的FLOYD]
- 00002、div的文字垂直居中与背景的渐变
- 【Linux】添加sudo用户、sudo用戶組
- Concat
- 黄聪:如何正确在Vue框架里使用Swiper
- 看CES 2017上有哪些好玩的物联网设备
- Python代码编写规范
- 【python】如何将ipdb的python解释器路径切换至虚拟环境中
- centos6.5修改yum安装的mysql默认目录
- Android开发——adb连接夜神模拟器