首页 > 代码库 > 【NOIP】提高组2012 同余方程
【NOIP】提高组2012 同余方程
【算法】扩展欧几里德算法
【题解】学完扩欧就可以随便水了。。。
转化为不定方程ax-by=1。
因为1且题目保证有解，所以方程有唯一解。
紫书曰：同余方程的一个解其实指的是一个同余等价类。
所以满足x≡x‘(mod b)的其他x‘也是方程的解。
题目求最小正整数解，因此ans=x%b。
#include<cstdio> #define ll long long void gcd(ll a,ll b,ll& g,ll& x,ll& y) { if(!b){g=a;x=1,y=0;} else{gcd(b,a%b,g,y,x);y-=x*(a/b);} } int main() { ll A,B; scanf("%lld %lld",&A,&B); ll G,X,Y; gcd(A,B,G,X,Y); printf("%lld",(X+B)%B); return 0; }
【NOIP】提高组2012 同余方程
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。