洛谷 P1082 同余方程（同余&&exgcd）
2024-08-28 05:19:47
嗯...
题目链接：https://www.luogu.org/problem/P1082
这道题很明显涉及到了同余和exgcd的问题，下面推导一下：
首先证明有解情况：
ax + by = m有解的必要条件是 m mod gcd(a, b) = 0
a为gcd(a, b)的倍数，b为gcd(a, b)的倍数，x、y为整数，
所以ax + by是gcd(a, b)的倍数，所以m是gcd(a, b)的倍数
然后证明a、b互质（下面会用到）：
本题中1 mod gcd(a, b) = 0，所以gcd(a, b) = 1，所以a、b互质
同余：
a≡b(mod n) --> 含义：a和b关于模n同余，即 a mod n = b mod n。
所以不难推出，a≡b的充要条件是a-b是n的整数倍（a > b）。
因为a-b是n的整数倍，所以a-b = ny（y为倍数）
所以，根据同余，我们可以把本题中的同余式转化为（注：这里的a.b与上文不同）：
ax≡1(modb) --> ax % b = 1 % b --> ax - 1 = by --> ax - by = 1
下一步，便进行exgcd（关于exgcd的证明见：https://www.luogu.org/problemnew/solution/P1082），分别求出ax - by = 1中x和y的值。
最后进行答案处理：
因为答案要求是x的最小正整数，所以我们进行一个答案处理：x = (x % b + b) % b
证明其正确性：
设新得到的x为xn，x = kb + q（q < b）则：
x % b = q ，把x % b = q带入 xn = (x % b + b) % b，得
xn = (x % b + b) % b = (q + b) % b = (q % b + b % b) % b = q % b = q
把xn = q带入x = kb + q，得，x = kb + xn， 所以xn = x - kb，然后再根据下面的推导得知它是正确的...
证明：
x批量地减去或加上 b，能保证 ax + by = ax + by = 1：
ax + by = 1
ax + by + k*ba - k*ba = 1
a (x + kb) + (y - ka) b = 1
1.显然这并不会把方程中任何整数变成非整数。
2.“加上或减去 b”不会使 x 错过任何解。可以这么理解：
已经求出一组整数 x,y 使得 ax+by =1 ，也就是(1 - ax) / b = y。y 是整数，可见目前 1−ax 是 b 的倍数。现在想改变 x并使得方程仍然成立。
已知 a,b 互质，假若x的变化量Δx不是b的倍数，则1−ax 的变化量−a*Δx也不是 bb 的倍数，这会使得1-ax不再是b的倍数，则y不是整数了。
仅当x的变化量是b的倍数时，1−ax能保持自己是b的倍数，此时就出现新的解了。
AC代码：
#include<cstdio>
#include<iostream> using namespace std;
//ax % b == 1 % b --> ax - 1 = y * b --> ax - yb == 1 long long d, x, y; inline void exgcd(long long a, long long b, long long &d, long long &x, long long &y){
if(!b) {d = a; x = ; y = ;}
else{ exgcd(b, a % b, d, y, x); y -= x * (a / b);}
}
int main(){
long long a,b;
scanf("%lld%lld", &a, &b);
exgcd(a, b, d, x, y);
x = (x % b + b) % b;
printf("%lld", x);
return ;
}
AC代码
最新文章
- 企业IT架构介绍
- WebAPI学习点滴(一)
- Python>>>使用Python和Pygame创建画板
- 实例变量和静态变量（或类变量static）
- XML与 HTML
- 循环多少次?[HDU1799]
- iOS应用程序间共享数据
- MySQL 5.7.9多源复制报错修复
- web服务器决定支持多少人同时在线的因素
- CREELINKS平台_处理器CeAd资源使用说明(CeAd的配置与使用)
- Spring4 事务管理
- 彻底解决Yii2中网页刷新时验证码不刷新的问题
- CSAPP缓冲区溢出攻击实验(下)
- tcp没用吗？为什么MOBA、“吃鸡”游戏不推荐用tcp协议
- (7/24) 插件配置之html文件的打包发布
- Angular、React.js 和Node.js到底选谁?
- 使用COE脚本绑定SQL Profile
- 嵌套函数变量修改nonlocal & 全局变量修改global
- 产品密钥无法激活成功，最后使用visio2013激活软件激活成功。
- NGINX防御CC攻击教程