diff options
| author | Paul Jungeblut <s_jungeb@i08pc38.atis-stud.uni-karlsruhe.de> | 2014-11-14 15:29:22 +0100 |
|---|---|---|
| committer | Paul Jungeblut <s_jungeb@i08pc38.atis-stud.uni-karlsruhe.de> | 2014-11-14 15:29:22 +0100 |
| commit | 8ceb0e35278563a3b315f04fc60fc9086d6c7a8a (patch) | |
| tree | a7b0e1928632be9a139aefa20e426490dfd12c90 /math/extendedEuclid.cpp | |
| parent | 1d2d2541dd913892a983da13f84c33f1a5d43ff6 (diff) | |
bellmann ford, gcd, lcm, ectended euclid
Diffstat (limited to 'math/extendedEuclid.cpp')
| -rw-r--r-- | math/extendedEuclid.cpp | 11 |
1 files changed, 11 insertions, 0 deletions
diff --git a/math/extendedEuclid.cpp b/math/extendedEuclid.cpp new file mode 100644 index 0000000..6d9490f --- /dev/null +++ b/math/extendedEuclid.cpp @@ -0,0 +1,11 @@ +//Accepted in Aufgabe mit Forderung: |X|+|Y| minimal (primaer) und X<=Y (sekundaer) +//hab aber keinen Beweis dafuer :) +ll x, y, d; //a * x + b * y = d = ggT(a,b) +void extendedEuclid(ll a, ll b) { + if (!b) { + x = 1; y = 0; d = a; return; + } + extendedEuclid(b, a % b); + ll x1 = y; ll y1 = x - (a / b) * y; + x = x1; y = y1; +}
\ No newline at end of file |