#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll x,y,a,b;
void exgcd(ll a, ll b)
{
if(b==0)
{
x=1;
y=0;
return ;
}
exgcd(b,a%b);
ll t=x;
x=y;
y=t-a/b*y;
return ;
}
int main()
{
ll a,b;
while(cin>>a>>b)
{
exgcd(a,b);
cout<<(x+b)%b<<endl;
}
}
求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。
2022-11-28
257
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《
阿里云开发者社区用户服务协议》和
《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写
侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：
求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。
目录
相关文章
|
7月前
|
算法
|
7月前
|
7月前
|
人工智能
SDN
|
7月前
|
7月前
|
JavaScript
|
机器学习/深度学习
欧拉函数：求小于等于n且与n互质的数的个数
求小于等于n且与n互质的数的个数
互质穷举法
互质：两个数互质代表两者最大公约数为1
最大公约数求法：辗转相除法，最小公倍数：较大值除以最大公约数乘以较小值
辗转相除法：
较大的数a取模较小的数b，得取模值c
若取模值等于0 则最大公约数为取模值，否则继续下一步
a与c再次取模，回到第二步
//求最大公约数gcd以及最大公倍数lcm
// 36 24 36/24
// 24 12 24/12
// 0 结束最大公约数为12
// 求最小公倍数
// lcm(a, b) = (a * b)/g
154
0
0
|
Java
热门文章
最新文章
1
《Stata统计分析与应用（第2版）》一3.4 图形的保存、合并及修改
2
Maven 3.6.3 的下载、安装、配置、检测（详细讲解）
3
基于区块链的机器学习模型创建方案
4
WPF listview item mouse enter/over popup
5
DevExpress 10.2.4系列-ASPxListBox根据列值不同设置不同图标
6
[Spring]支持注解的Spring调度器
7
红帽7.4新增的安全特性
8
hdu 1800 Flying to the Mars
9
研究 flex 4 开发后台管理项目（1）
10
Error: XML response that was returned...
1
《docker高级篇（大厂进阶）：2.DockerFile解析》包括：是什么、DockerFile构建过程解析、DockerFile常用保留字指令、案例、小总结
115
2
《Java 人工智能开发：Eclipse 与 IntelliJ IDEA 双雄助力》
46
3
《Java 在开源 AI 框架中的中流砥柱角色》
34
4
《Java 与大数据框架：AI 数据预处理的强力联盟》
39
5
《Java 优化秘籍：计算密集型 AI 任务加速指南》
35
6
《Java 与 OpenAI 协同：开启智能编程新范式》
31
7
uniapp开发鸿蒙，是前端新出路吗？
30
8
鸿蒙(HarmonyOS)原生AI能力之文本识别
39
9
鸿蒙开发之PixelMap介绍与实现图片变换
34
10
鸿蒙(HarmonyOS)开发之无须申请权限写入图片到相册
40