Extended Euclid Recursive Algorithm how works

একটি সাধারণ ইউক্লিডিয়ান এলগোরিদম নিচের কোডে ইম্পলিমেন্ট করা হয়েছে............। খুবই সাধারণ একটি রিকার্সন...
Extended Euclid theorem থেকে আমরা জানি যদি a এবং b এর জন্য এমন একটি সমীকরণ পাওয়া যাবে যেনো sa + tb

1 2 3 4 5 6 7 8 9 10 11

typedef pair<int, int> pii; #define x first #define y second pii extendedEuclid(int a, int b) { // returns x, y | ax + by = gcd(a,b) if(b == 0) return pii(1, 0); else { pii d = extendedEuclid(b, a % b); return pii(d.y, d.x - d.y * (a / b)); } }