src/nt/gl/exgcd/lib.hpp - GCC Code Coverage Report

Directory:	./
Coverage:	low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%

	Coverage	Exec / Excl / Total
Lines:	84.5%	87 / 0 / 103
Functions:	100.0%	6 / 0 / 6
Branches:	75.8%	91 / 0 / 120

    src/nt/gl/exgcd/lib.hpp
    
        Line
        Branch
        Exec
        Source
      
        #pragma once
      
        #include "../../../util/traits/math/lib.hpp"
      
        namespace tifa_libs {
      
        // Binary exgcd
      
        template <uint_c U, bool only_x = false>
      
        844088828
        CEXP auto exgcd_b(U a, U b) NE {
      
          using T = to_sint_t<U>;
      
          if CEXP (only_x) {
      
          3/4auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 9843 times.
auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long):
✓ Branch 0 taken 5402270 times.
✓ Branch 1 taken 838676683 times.

        844088796
            if (!a) return std::make_tuple(b, (T)0);
      
          2/4auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 9843 times.
auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long):
✗ Branch 0 not taken.
✓ Branch 1 taken 838676683 times.

        838686526
            if (!b) return std::make_tuple(a, (T)1);
      
          } else {
      
          1/2✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.

        32
            if (!a) return std::make_tuple(b, (T)0, (T) !!b);
      
          1/2✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.

        32
            if (!b) return std::make_tuple(a, (T)1, (T)0);
      
          }
      
        838686558
          auto r = std::__countr_zero(a | b);
      
        838686558
          a >>= r, b >>= r;
      
        838686558
          T x = (T)a, y = (T)b, s = 1, t = 0, u = 0, v = 1;
      
          6/6auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int):
✓ Branch 0 taken 151894 times.
✓ Branch 1 taken 9843 times.
auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long):
✓ Branch 0 taken 462 times.
✓ Branch 1 taken 32 times.
auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long):
✓ Branch 0 taken 16418870227 times.
✓ Branch 1 taken 838676683 times.

        17257709141
          while (x) {
      
          6/6auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int):
✓ Branch 0 taken 58416 times.
✓ Branch 1 taken 151894 times.
auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long):
✓ Branch 0 taken 367 times.
✓ Branch 1 taken 462 times.
auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long):
✓ Branch 0 taken 12057972858 times.
✓ Branch 1 taken 16418870227 times.

        28477054224
            while (!(x & 1))
      
          6/6auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int):
✓ Branch 0 taken 18738 times.
✓ Branch 1 taken 39678 times.
auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long):
✓ Branch 0 taken 190 times.
✓ Branch 1 taken 177 times.
auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long):
✓ Branch 0 taken 3382931560 times.
✓ Branch 1 taken 8675041298 times.

        12058031641
              if (x /= 2; !((s | t) & 1)) s /= 2, t /= 2;
      
        8675081153
              else s = (s + (T)b) / 2, t = (t - (T)a) / 2;
      
          6/6auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int):
✓ Branch 0 taken 235201 times.
✓ Branch 1 taken 151894 times.
auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long):
✓ Branch 0 taken 423 times.
✓ Branch 1 taken 462 times.
auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long):
✓ Branch 0 taken 19551573290 times.
✓ Branch 1 taken 16418870227 times.

        35970831497
            while (!(y & 1))
      
          6/6auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int):
✓ Branch 0 taken 141252 times.
✓ Branch 1 taken 93949 times.
auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long):
✓ Branch 0 taken 199 times.
✓ Branch 1 taken 224 times.
auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long):
✓ Branch 0 taken 9871065707 times.
✓ Branch 1 taken 9680507583 times.

        19551808914
              if (y /= 2; !((u | v) & 1)) u /= 2, v /= 2;
      
        9680601756
              else u = (u + (T)b) / 2, v = (v - (T)a) / 2;
      
          6/6auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int):
✓ Branch 0 taken 48344 times.
✓ Branch 1 taken 103550 times.
auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long):
✓ Branch 0 taken 226 times.
✓ Branch 1 taken 236 times.
auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long):
✓ Branch 0 taken 6649964180 times.
✓ Branch 1 taken 9768906047 times.

        16419022583
            if (x >= y) x -= y, s -= u, t -= v;
      
        9769009833
            else y -= x, u -= s, v -= t;
      
          }
      
          5/6auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 9843 times.
auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long):
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 29 times.
auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long):
✓ Branch 0 taken 3080 times.
✓ Branch 1 taken 838673603 times.

        838686558
          if (y > 1) a /= (U)y, b /= (U)y;
      
          13/18auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int):
✓ Branch 0 taken 9843 times.
✗ Branch 1 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 9843 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 9843 times.
auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long):
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 4 times.
✓ Branch 4 taken 28 times.
✓ Branch 5 taken 4 times.
✓ Branch 6 taken 28 times.
auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long):
✓ Branch 0 taken 838676683 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 3071789 times.
✓ Branch 4 taken 835604894 times.
✓ Branch 5 taken 3071789 times.
✓ Branch 6 taken 835604894 times.

        838686558
          if (a && (U)abs(v) >= a) {
      
        3071793
            const T _ = v / (T)a;
      
        3071793
            v -= _ * (T)a, u += _ * (T)b;
      
          }
      
          11/18auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int):
✓ Branch 0 taken 9843 times.
✗ Branch 1 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 9843 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 9843 times.
auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long):
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 30 times.
✓ Branch 5 taken 2 times.
✓ Branch 6 taken 30 times.
auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long):
✓ Branch 0 taken 838676683 times.
✗ Branch 1 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 838676683 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 838676683 times.

        838686558
          if (b && (U)abs(u) >= b) {
      
        2
            const T _ = u / (T)b;
      
        2
            u -= _ * (T)b, v += _ * (T)a;
      
          }
      
          5/6auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int):
✗ Branch 4 not taken.
✓ Branch 5 taken 9843 times.
auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long):
✓ Branch 4 taken 3 times.
✓ Branch 5 taken 29 times.
auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long):
✓ Branch 4 taken 8396652 times.
✓ Branch 5 taken 830280031 times.

        838686558
          if (const T u_ = u + (T)b, v_ = v - (T)a; abs(u_) + abs(v_) <= abs(u) + abs(v)) u = u_, v = v_;
      
          5/6auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int):
✗ Branch 4 not taken.
✓ Branch 5 taken 9843 times.
auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long):
✓ Branch 4 taken 12 times.
✓ Branch 5 taken 20 times.
auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long):
✓ Branch 4 taken 251185918 times.
✓ Branch 5 taken 587490765 times.

        838686558
          if (const T u_ = u - (T)b, v_ = v + (T)a; abs(u_) + abs(v_) <= abs(u) + abs(v)) u = u_, v = v_;
      
        838686526
          if CEXP (only_x) return std::make_tuple(U(y << r), u);
      
        32
          else return std::make_tuple(U(y << r), u, v);
      
        }
      
        // @return then return tuple(g, x[, y]) s.t. g = gcd(a, b), xa + yb = g, |x| + |y| is the minimal (primary) and x <= y (secondarily)
      
        template <sint_c T, bool only_x = false>
      
        2576006545
        CEXP auto exgcd(T a, T b) NE {
      
          using U = to_uint_t<T>;
      
          7/12auto tifa_libs::exgcd<int, true>(int, int):
✓ Branch 1 taken 1447272605 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 7747 times.
✓ Branch 4 taken 1447264858 times.
auto tifa_libs::exgcd<long, false>(long, long):
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 32 times.
✗ Branch 4 not taken.
auto tifa_libs::exgcd<long, true>(long, long):
✓ Branch 1 taken 582945993 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 582945993 times.
✗ Branch 4 not taken.

        2576006545
          if (auto [x, y] = minmax(a, b); x >= 0 && y <= T(U(-1) >> sizeof(U))) return exgcd_b<U, only_x>((U)a, (U)b);
      
          if CEXP (only_x) {
      
        1731917717
            T s = 1, u = 0;
      
          2/4auto tifa_libs::exgcd<int, true>(int, int):
✓ Branch 0 taken 19741457193 times.
✓ Branch 1 taken 1447264858 times.
auto tifa_libs::exgcd<long, true>(long, long):
✗ Branch 0 not taken.
✗ Branch 1 not taken.

        25493981656
            while (b) {
      
        23762063939
              T c = a / b;
      
        23762063939
              std::tie(s, u, a, b) = std::make_tuple(u, s - u * c, b, a - b * c);
      
            }
      
        1731917717
            return std::make_tuple((U)a, s);
      
          } else {
      
        ✗
            T s = 1, t = 0, u = 0, v = 1;
      
        ✗
            while (b) {
      
        ✗
              T c = a / b;
      
        ✗
              std::tie(s, t, u, v, a, b) = std::make_tuple(u, v, s - u * c, t - v * c, b, a - b * c);
      
            }
      
        ✗
            return std::make_tuple((U)a, s, t);
      
          }
      
        }
      
        }  // namespace tifa_libs

Line	Branch	Exec	Source
1			#pragma once
2
3			#include "../../../util/traits/math/lib.hpp"
4
5			namespace tifa_libs {
6
7			// Binary exgcd
8			template <uint_c U, bool only_x = false>
9		844088828	CEXP auto exgcd_b(U a, U b) NE {
10			using T = to_sint_t<U>;
11			if CEXP (only_x) {
12	3/4 auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int): ✗ Branch 0 not taken. ✓ Branch 1 taken 9843 times. auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long): ✓ Branch 0 taken 5402270 times. ✓ Branch 1 taken 838676683 times.	844088796	if (!a) return std::make_tuple(b, (T)0);
13	2/4 auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int): ✗ Branch 0 not taken. ✓ Branch 1 taken 9843 times. auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long): ✗ Branch 0 not taken. ✓ Branch 1 taken 838676683 times.	838686526	if (!b) return std::make_tuple(a, (T)1);
14			} else {
15	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 32 times.	32	if (!a) return std::make_tuple(b, (T)0, (T) !!b);
16	1/2 ✗ Branch 0 not taken. ✓ Branch 1 taken 32 times.	32	if (!b) return std::make_tuple(a, (T)1, (T)0);
17			}
18		838686558	auto r = std::__countr_zero(a \| b);
19		838686558	a >>= r, b >>= r;
20		838686558	T x = (T)a, y = (T)b, s = 1, t = 0, u = 0, v = 1;
21	6/6 auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int): ✓ Branch 0 taken 151894 times. ✓ Branch 1 taken 9843 times. auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long): ✓ Branch 0 taken 462 times. ✓ Branch 1 taken 32 times. auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long): ✓ Branch 0 taken 16418870227 times. ✓ Branch 1 taken 838676683 times.	17257709141	while (x) {
22	6/6 auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int): ✓ Branch 0 taken 58416 times. ✓ Branch 1 taken 151894 times. auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long): ✓ Branch 0 taken 367 times. ✓ Branch 1 taken 462 times. auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long): ✓ Branch 0 taken 12057972858 times. ✓ Branch 1 taken 16418870227 times.	28477054224	while (!(x & 1))
23	6/6 auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int): ✓ Branch 0 taken 18738 times. ✓ Branch 1 taken 39678 times. auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long): ✓ Branch 0 taken 190 times. ✓ Branch 1 taken 177 times. auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long): ✓ Branch 0 taken 3382931560 times. ✓ Branch 1 taken 8675041298 times.	12058031641	if (x /= 2; !((s \| t) & 1)) s /= 2, t /= 2;
24		8675081153	else s = (s + (T)b) / 2, t = (t - (T)a) / 2;
25	6/6 auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int): ✓ Branch 0 taken 235201 times. ✓ Branch 1 taken 151894 times. auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long): ✓ Branch 0 taken 423 times. ✓ Branch 1 taken 462 times. auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long): ✓ Branch 0 taken 19551573290 times. ✓ Branch 1 taken 16418870227 times.	35970831497	while (!(y & 1))
26	6/6 auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int): ✓ Branch 0 taken 141252 times. ✓ Branch 1 taken 93949 times. auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long): ✓ Branch 0 taken 199 times. ✓ Branch 1 taken 224 times. auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long): ✓ Branch 0 taken 9871065707 times. ✓ Branch 1 taken 9680507583 times.	19551808914	if (y /= 2; !((u \| v) & 1)) u /= 2, v /= 2;
27		9680601756	else u = (u + (T)b) / 2, v = (v - (T)a) / 2;
28	6/6 auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int): ✓ Branch 0 taken 48344 times. ✓ Branch 1 taken 103550 times. auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long): ✓ Branch 0 taken 226 times. ✓ Branch 1 taken 236 times. auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long): ✓ Branch 0 taken 6649964180 times. ✓ Branch 1 taken 9768906047 times.	16419022583	if (x >= y) x -= y, s -= u, t -= v;
29		9769009833	else y -= x, u -= s, v -= t;
30			}
31	5/6 auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int): ✗ Branch 0 not taken. ✓ Branch 1 taken 9843 times. auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long): ✓ Branch 0 taken 3 times. ✓ Branch 1 taken 29 times. auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long): ✓ Branch 0 taken 3080 times. ✓ Branch 1 taken 838673603 times.	838686558	if (y > 1) a /= (U)y, b /= (U)y;
32	13/18 auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int): ✓ Branch 0 taken 9843 times. ✗ Branch 1 not taken. ✗ Branch 3 not taken. ✓ Branch 4 taken 9843 times. ✗ Branch 5 not taken. ✓ Branch 6 taken 9843 times. auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long): ✓ Branch 0 taken 32 times. ✗ Branch 1 not taken. ✓ Branch 3 taken 4 times. ✓ Branch 4 taken 28 times. ✓ Branch 5 taken 4 times. ✓ Branch 6 taken 28 times. auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long): ✓ Branch 0 taken 838676683 times. ✗ Branch 1 not taken. ✓ Branch 3 taken 3071789 times. ✓ Branch 4 taken 835604894 times. ✓ Branch 5 taken 3071789 times. ✓ Branch 6 taken 835604894 times.	838686558	if (a && (U)abs(v) >= a) {
33		3071793	const T _ = v / (T)a;
34		3071793	v -= _ * (T)a, u += _ * (T)b;
35			}
36	11/18 auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int): ✓ Branch 0 taken 9843 times. ✗ Branch 1 not taken. ✗ Branch 3 not taken. ✓ Branch 4 taken 9843 times. ✗ Branch 5 not taken. ✓ Branch 6 taken 9843 times. auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long): ✓ Branch 0 taken 32 times. ✗ Branch 1 not taken. ✓ Branch 3 taken 2 times. ✓ Branch 4 taken 30 times. ✓ Branch 5 taken 2 times. ✓ Branch 6 taken 30 times. auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long): ✓ Branch 0 taken 838676683 times. ✗ Branch 1 not taken. ✗ Branch 3 not taken. ✓ Branch 4 taken 838676683 times. ✗ Branch 5 not taken. ✓ Branch 6 taken 838676683 times.	838686558	if (b && (U)abs(u) >= b) {
37		2	const T _ = u / (T)b;
38		2	u -= _ * (T)b, v += _ * (T)a;
39			}
40	5/6 auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int): ✗ Branch 4 not taken. ✓ Branch 5 taken 9843 times. auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long): ✓ Branch 4 taken 3 times. ✓ Branch 5 taken 29 times. auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long): ✓ Branch 4 taken 8396652 times. ✓ Branch 5 taken 830280031 times.	838686558	if (const T u_ = u + (T)b, v_ = v - (T)a; abs(u_) + abs(v_) <= abs(u) + abs(v)) u = u_, v = v_;
41	5/6 auto tifa_libs::exgcd_b<unsigned int, true>(unsigned int, unsigned int): ✗ Branch 4 not taken. ✓ Branch 5 taken 9843 times. auto tifa_libs::exgcd_b<unsigned long, false>(unsigned long, unsigned long): ✓ Branch 4 taken 12 times. ✓ Branch 5 taken 20 times. auto tifa_libs::exgcd_b<unsigned long, true>(unsigned long, unsigned long): ✓ Branch 4 taken 251185918 times. ✓ Branch 5 taken 587490765 times.	838686558	if (const T u_ = u - (T)b, v_ = v + (T)a; abs(u_) + abs(v_) <= abs(u) + abs(v)) u = u_, v = v_;
42		838686526	if CEXP (only_x) return std::make_tuple(U(y << r), u);
43		32	else return std::make_tuple(U(y << r), u, v);
44			}
45			// @return then return tuple(g, x[, y]) s.t. g = gcd(a, b), xa + yb = g, \|x\| + \|y\| is the minimal (primary) and x <= y (secondarily)
46			template <sint_c T, bool only_x = false>
47		2576006545	CEXP auto exgcd(T a, T b) NE {
48			using U = to_uint_t<T>;
49	7/12 auto tifa_libs::exgcd<int, true>(int, int): ✓ Branch 1 taken 1447272605 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 7747 times. ✓ Branch 4 taken 1447264858 times. auto tifa_libs::exgcd<long, false>(long, long): ✓ Branch 1 taken 32 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 32 times. ✗ Branch 4 not taken. auto tifa_libs::exgcd<long, true>(long, long): ✓ Branch 1 taken 582945993 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 582945993 times. ✗ Branch 4 not taken.	2576006545	if (auto [x, y] = minmax(a, b); x >= 0 && y <= T(U(-1) >> sizeof(U))) return exgcd_b<U, only_x>((U)a, (U)b);
50			if CEXP (only_x) {
51		1731917717	T s = 1, u = 0;
52	2/4 auto tifa_libs::exgcd<int, true>(int, int): ✓ Branch 0 taken 19741457193 times. ✓ Branch 1 taken 1447264858 times. auto tifa_libs::exgcd<long, true>(long, long): ✗ Branch 0 not taken. ✗ Branch 1 not taken.	25493981656	while (b) {
53		23762063939	T c = a / b;
54		23762063939	std::tie(s, u, a, b) = std::make_tuple(u, s - u * c, b, a - b * c);
55			}
56		1731917717	return std::make_tuple((U)a, s);
57			} else {
58		✗	T s = 1, t = 0, u = 0, v = 1;
59		✗	while (b) {
60		✗	T c = a / b;
61		✗	std::tie(s, t, u, v, a, b) = std::make_tuple(u, v, s - u * c, t - v * c, b, a - b * c);
62			}
63		✗	return std::make_tuple((U)a, s, t);
64			}
65			}
66
67			} // namespace tifa_libs
68