首页 > 【模板】同余方程
开通博客写题解
头像 猫萌
发表于 2021-10-27 21:58:00
简单的模板题。利用扩展欧几里得即可求。 首先，你要知道在初等数论里，我们把a和b的最大公约数记错记作(a,b)，把b可被a整除记作a|b,把b不可被a整除记作a∤b 扩展欧几里得的证明需要用翡蜀定理 对任意的正整数a b，必然存在x y，使得ax+by=(a,b) 若b=0，那么（a,b）=a。此 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 andif
发表于 2023-08-20 13:53:51
题意 给你一个同余方程 ，让你求最小正整数解，无解的话，输出-1 思路 同余方程可以等价于 （不知道为什么这边的加法失效了）,简单移项可以得到 ，那么我们就可以拓展欧几里得来求解了 注意事项 拓展欧几里得的解不一定是最小正整数解，我们需要转化下 代码 #include<bits/stdc++. 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 陌研
发表于 2021-10-29 00:54:46
【同余方程】 模板题，直接用exgcd就行了，上一场的青蛙的约会搞懂了，自然就会了。 #include <bits/stdc++.h> #define int long long using namespace std; int exgcd(int a, int b, int& 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”