acl_cpp.math

from acl_cpp.math import crt, floor_sum

pow_mod

Use pow(x, n, mod) instead.

inv_mod

Use pow(x, -1, mod) instead.

math.crt

# pair<ll, ll> crt(vector<ll> r, vector<ll> m)
def crt(r: list[int], m: list[int]) -> tuple[int, int]

Given two arrays \(r, m\) with length \(n\), solves the modular equation system

\[x \equiv r[i] \pmod{m[i]}, \forall i \in \lbrace 0,1,\cdots, n - 1 \rbrace\]

If there is no solution, returns \((0, 0)\). Otherwise, all the solutions can be written as the form \(x \equiv y \pmod z\) where \(y, z (0 \leq y < z = \mathrm{lcm}(m[i]))\). Returns \((y, z)\) as a pair. If \(n=0\), returns \((0, 1)\).

Constraints

\(\text{len}(r) = \text{len}(m)\)
\(-2^{63} \le r[i] < 2^{63}\)
\(1 \le m[i] < 2^{63}\)
\(\mathrm{lcm}(m[i]) < 2^{63}\)

Behavior is undefined if \(\mathrm{lcm}(m[i]) < 2^{63}\) is not satisfied.

Complexity

\(O(n \log \mathrm{lcm}(m[i]))\)

math.floor_sum

# ll floor_sum(ll n, ll m, ll a, ll b)
def floor_sum(n: int, m: int, a: int, b: int) -> int

Returns the following sum:

\[\sum_{i = 0}^{n - 1} \left\lfloor \frac{a \times i + b}{m} \right\rfloor\]

If the result does not fit in a 64-bit signed integer, returns the value modulo \(2^{64}\).

Constraints

\(0 \le n \lt 2^{32}\)
\(1 \le m \lt 2^{32}\)

Complexity

\(O(\log m)\)

internal.math

Source code

from acl_cpp.internal.math import is_prime, primitive_root

internal.math.is_prime

# bool is_prime_constexpr(int n)
def is_prime(n: int) -> bool

Returns whether \(n\) is a prime number.

Constraints

\(0 \le n < 2^{31}\)

internal.math.primitive_root

# int primitive_root_constexpr(int m)
def primitive_root(m: int) -> int

Returns one of the primitive roots modulo \(m\).

Constraints

\(2 \le m < 2^{31}\)
\(m\) is a prime number

Examples

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_c

from acl_cpp.math import floor_sum

T = int(input())
for _ in range(T):
    N, M, A, B = map(int, input().split())
    print(floor_sum(N, M, A, B))