number

ソースコード

from titan_pylib.math.number import ext_gcd
from titan_pylib.math.number import linear_indeterminate_equation
from titan_pylib.math.number import crt
from titan_pylib.math.number import lcm
from titan_pylib.math.number import lcm_mul
from titan_pylib.math.number import totient_function
from titan_pylib.math.number import fastpow
from titan_pylib.math.number import modinv
from titan_pylib.math.number import isqrt
from titan_pylib.math.number import lcm_mod
from titan_pylib.math.number import div_mod
from titan_pylib.math.number import large_pow
from titan_pylib.math.number import mat_mul
from titan_pylib.math.number import mat_powmod

view on github

展開済みコード

  1# 展開に失敗しました
  2def ext_gcd(a: int, b: int) -> tuple[int, int, int]:
  3    """gcdと、ax + by = gcd(a, b)なるx,yを返す / O(log(min(|a|, |b|)))
  4
  5    Args:
  6        a (int):
  7        b (int):
  8
  9    Returns:
 10        tuple[int, int, int]: (gcd, x, y)
 11    """
 12    if b == 0:
 13        return a, 1, 0
 14    d, y, x = ext_gcd(b, a % b)
 15    y -= a // b * x
 16    if x < 0:
 17        x += b // d
 18        y -= a // d
 19    # assert a * x + b * y == d
 20    return d, x, y
 21
 22
 23def linear_indeterminate_equation(a: int, b: int, c: int) -> tuple[int, int, int]:
 24    """`ax + by = c` の整数解を返す"""
 25    g, x, y = ext_gcd(a, b)
 26    if c % g != 0:
 27        return None, None, None
 28    c //= g
 29    return g, x * c, y * c
 30
 31
 32def crt(B: list[int], M: list[int]) -> tuple[int, int]:
 33    """中国剰余定理 / O(nlog(lcm(M)))
 34    ```
 35    a == B[0] (mod M[0])
 36    a == B[1] (mod M[1])
 37    ...
 38    ```
 39
 40    となるような、 `a == r (mod lcm(M))` を返す
 41
 42
 43    Returns:
 44        tuple[int, int]: `m == -1` のとき解なし。
 45    """
 46    assert len(B) == len(M)
 47    r, lcm = 0, 1
 48    for i in range(len(B)):
 49        d, x, _ = ext_gcd(lcm, M[i])
 50        if (B[i] - r) % d != 0:
 51            return (0, -1)
 52        tmp = (B[i] - r) // d * x % (M[i] // d)
 53        r += lcm * tmp
 54        lcm *= M[i] // d
 55    return (r, lcm)
 56
 57
 58import math
 59
 60
 61def lcm(a: int, b: int) -> int:
 62    return a // math.gcd(a, b) * b
 63
 64
 65def lcm_mul(A: list[int]) -> int:
 66    assert len(A) > 0
 67    ans = 1
 68    for a in A:
 69        ans = lcm(ans, a)
 70    return ans
 71
 72
 73def totient_function(n: int) -> int:
 74    """1からnまでの自然数の中で、nと互いに素なものの個数 / O(√N)"""
 75    assert n > 0
 76    ans = n
 77    i = 2
 78    while i * i <= n:
 79        if n % i == 0:
 80            ans -= ans // i
 81            while n % i == 0:
 82                n //= i
 83        i += 1
 84    if n > 1:
 85        ans -= ans // n
 86    return ans
 87
 88
 89mod = "998244353"
 90
 91
 92def fastpow(a: int, b: int) -> int:
 93    res = 1
 94    while b:
 95        if b & 1:
 96            res = res * a % mod
 97        a = a * a % mod
 98        b >>= 1
 99    return res
100
101
102def modinv(a, mod):
103    b = mod
104    x, y, u, v = 1, 0, 0, 1
105    while b:
106        k = a // b
107        x -= k * u
108        y -= k * v
109        x, u = u, x
110        y, v = v, y
111        a, b = b, a % b
112    x %= mod
113    return x
114
115
116def isqrt(n: int) -> int:
117    assert n >= 0
118    if n == 0:
119        return 0
120    x = 1 << (n.bit_length() + 1) >> 1
121    y = (x + n // x) >> 1
122    while y < x:
123        x, y = y, (y + n // y) >> 1
124    return x
125
126
127"Return LCM % mod"
128from collections import Counter
129from titan_pylib.math.divisors import Osa_k
130
131
132def lcm_mod(o: Osa_k, A: list, mod: int) -> int:
133    cou = Counter()
134    for a in A:
135        for k, v in Counter(o.p_factorization(a)).items():
136            cou[k] = max(cou[k], v)
137    lcm = 1
138    for k, v in cou.items():
139        lcm *= pow(k, v, mod)
140        lcm %= mod
141    return lcm % mod
142
143
144#  -----------------------  #
145
146"Return (a // b) % mod"
147"O(1), mod: prime"
148
149
150def div_mod(a: int, b: int, mod: int) -> int:
151    "Return (a // b) % mod"
152    return (a % mod) * pow(b, mod - 2, mod) % mod
153
154
155#  -----------------------  #
156
157
158def large_pow(a, b, c, mod):
159    "return (a^(b^c)) % mod. p: prime."
160    if a % mod == 0:
161        return 0
162    return pow(a, pow(b, c, mod - 1), mod)
163
164
165#  -----------------------  #
166
167
168def mat_mul(A: list, B: list, mod: int) -> list:
169    l, m = len(A), len(A[0])
170    n = len(B[0])
171    assert m == len(B)
172    return [
173        [sum([A[i][k] * B[k][j] for k in range(m)]) % mod for j in range(n)]
174        for i in range(l)
175    ]
176
177
178def mat_powmod(A: list, n: int, mod: int) -> list:
179    res = [[0] * len(A) for _ in range(len(A))]
180    for i in range(len(A)):
181        res[i][i] = 1
182    while n > 0:
183        if n & 1 == 1:
184            res = mat_mul(A, res, mod)
185        A = mat_mul(A, A, mod)
186        n >>= 1
187    return res
188
189
190#  -----------------------  #

仕様

crt(B: list[int], M: list[int]) → tuple[int, int][source]

中国剰余定理 / O(nlog(lcm(M))) ` a == B[0] (mod M[0]) a == B[1] (mod M[1]) ... `

となるような、 a == r (mod lcm(M)) を返す

Returns:

m == -1 のとき解なし。

Return type:

tuple[int, int]

div_mod(a: int, b: int, mod: int) → int[source]

Return (a // b) % mod

ext_gcd(a: int, b: int) → tuple[int, int, int][source]

gcdと、ax + by = gcd(a, b)なるx,yを返す / O(log(min(|a|, |b|)))

Parameters:

  • a (int)

  • b (int)

Returns:

(gcd, x, y)

Return type:

tuple[int, int, int]

fastpow(a: int, b: int) → int[source]
isqrt(n: int) → int[source]
large_pow(a, b, c, mod)[source]

return (a^(b^c)) % mod. p: prime.

lcm(a: int, b: int) → int[source]
lcm_mod(o: Osa_k, A: list, mod: int) → int[source]
lcm_mul(A: list[int]) → int[source]
linear_indeterminate_equation(a: int, b: int, c: int) → tuple[int, int, int][source]

ax + by = c の整数解を返す

mat_mul(A: list, B: list, mod: int) → list[source]
mat_powmod(A: list, n: int, mod: int) → list[source]
modinv(a, mod)[source]
totient_function(n: int) → int[source]

1からnまでの自然数の中で、nと互いに素なものの個数 / O(√N)