diff options
Diffstat (limited to 'content/other/recover.cpp')
| -rw-r--r-- | content/other/recover.cpp | 15 |
1 files changed, 8 insertions, 7 deletions
diff --git a/content/other/recover.cpp b/content/other/recover.cpp index 0d3c3ea..1a593f0 100644 --- a/content/other/recover.cpp +++ b/content/other/recover.cpp @@ -1,12 +1,13 @@ ll sq(ll x) {return x*x;} -pair<ll, ll> recover(ll c, ll m) { - array<ll, 3> u = {1, 0, m}, v = {0, 1, c}; - while (m <= 2 * sq(v[2])) { - ll q = u[2] / v[2]; - for (int i : {0, 1, 2}) u[i] -= q * v[i]; +array<ll, 2> recover(ll c, ll m) { + array<ll, 2> u = {m, 0}, v = {c, 1}; + while (m <= 2 * sq(v[0])) { + ll q = u[0] / v[0]; + u[0] -= q * v[0]; + u[1] -= q * v[1]; swap(u, v); } - if (v[1] < 0 || 2 * sq(v[1]) >= m) return {-1, -1}; - return {v[2], v[1]}; + if (v[1] <= 0 || 2 * sq(v[1]) >= m) return {-1, -1}; + return v; } |