finds x such that x % m1 = a1, x % m2 = a2. m1 and m2 may not be coprime here, x is unique modulo m = lcm(m1, m2). returns (x, m). on failure, m = -1.

find z such that z % x = a, z % y = b. here, z is unique modulo M = lcm(x,y). returns (z, M). on failure, M = -1.

finds x such that x % m1 = a1, x % m2 = a2. m1 and m2 may not be coprime here, x is unique modulo m = lcm(m1, m2). returns (x, m). on failure, m = -1.

finds x such that x % m1 = a1, x % m2 = a2. m1 and m2 may not be coprime here, x is unique modulo m = lcm(m1, m2). returns (x, m). on failure, m = -1.

returns parents of each vertex each edge should be distinct it assumes that a solution exists (all vertices are reachable from root) 0 indexed Takes ~

O(n^2 + n*k) where k is the number of non-zero elements

check if two n*n matrix a*b=c within complexity (iteration*n^2) probability of error 2^(-iteration)

n = number of equations, m = number of variables

O(n^3 logn)

transformtation: a(i, j) = 0 for i > j + 1

count of numbers in [l, r] Less than or equal to k

generates the polynomial explicitely

generates the polynomial explicitely

p = first at least n + 1 points: a, a+d, ..., a+n*d of the n degree polynomial, returns f(x)

takes 0.8sec for n = 100000 Extracts the polynomial explicitely

generates the polynomial explicitely

generates the polynomial explicitely

runs under 0.5s for n = 1e12

runs under 0.2s for n = 1e12

transition -> for(i = 0; i < x; i++) f[n] += tr[i] * f[n-i-1] S contains initial values, k is 0 indexed

transition -> for(i = 0; i < x; i++) f[n] += tr[i] * f[n-i-1] S contains initial values, k is 0 indexed

each node should be unique in the adjacency list

find sqrt(a) % p, i.e. find any x such that x^2 = a (mod p) if a solution exist, then if a == 0 or p == 2, there are 1 solution, otherwise, there are

0 indexed returns the list of the three edge connected components O(n)

n equations of form: a_i*x_{i-1}+b_i*x_i+c_i*x_{i+1}=d_i, for i=1 to n where a_1=0,c_n=0 matrix form: b1 c1 0 0 0 | x1 d1 a2 b2 c2 0 0 |

thomas algorithm for solving tri-diagonal system of equations

returns the area of the intersection of the circle with center c and radius r and the triangle formed by the points c, a, b

possible points that can be generated are of the form (a * m, b * m + k * coeff) add (a[i], b[i])

add x * b^e to this number: x, e both can be negative O(log_b(n)^2 / K) amortized

w[u][v]++, w[v][u]++, deg[u]++,deg[v]++

range add query

returns any pair of segments such that they intersect

Assume that the sphere is centered at the origin the polygon is simple and given in counterclockwise order for each consecutive pair of points, the co

try to increment the size of the independent set implementation details: https://codeforces.com/blog/entry/69287#:~:text=Implementation%20and%20comple

it finds an augmented path starting from u

it finds an augmented path starting from u

ps-profits ws-weights ms-maximum limit of each element W-maximum weight O(n*W)

generate all powerful numbers and add up the results params: current prime index, current number generated, and h(m)

creating a treap for string s in O(n)