用什么软件建网站最方便,网站中信息更新怎么做的,八亿免费wap自助建站,北京企业官网建设为什么老是碰上 扩展欧几里德算法 ( •̀∀•́ )最讨厌数论了 看来是时候学一学了 度娘百科说#xff1a; 首先#xff0c; axby gcd(a, b) 这个公式肯定有解 #xff08;( •̀∀•́ )她说根据数论中的相关定理可以证明#xff0c;反正我信了#xff09; 所以 axby g…为什么老是碰上 扩展欧几里德算法 ( •̀∀•́ )最讨厌数论了 看来是时候学一学了 度娘百科说 首先 axby gcd(a, b) 这个公式肯定有解 ( •̀∀•́ )她说根据数论中的相关定理可以证明反正我信了 所以 axby gcd(a, b) * k 也肯定有解 废话把x和y乘k倍就好了 所以这个公式我们写作axby d(gcd(a, b) | d) gcd(a, b) | d表示d能整除gcd这个符号在数学上经常见 那么已知 ab 求 一组解 xy 满足 axby gcd(a, b) 这个公式 1 #includecstdio2 typedef long long LL;3 void extend_Eulid(LL a, LL b, LL x, LL y, LL d){4 if (!b) {d a, x 1, y 0;}5 else{6 extend_Eulid(b, a % b, y, x, d);7 y - x * (a / b);8 }9 }
10 int main(){
11 LL a, b, d, x, y;
12 while(~scanf(%lld%lld, a, b)){
13 extend_Eulid(a, b, x, y, d);
14 printf(%lld*a %lld*b %lld\n, x, y, d);
15 }
16 } 有些人喜欢极度简化这是病得治(,,• ₃ •,,)比如在下 1 void ex_gcd(LL a, LL b, LL d, LL x, LL y){
2 if(!b){d a; x 1; y 0;}
3 else{ex_gcd(b, a%b, d, y, x); y - x*(a/b);}
4 } 连名字都简化了。。。 ( •̀∀•́ )解完了 睡觉~~~ 转载于:https://www.cnblogs.com/linyujun/p/5167916.html
