Toán học

bool is_prime(long long n) {
    if (n<2) return false;
    for (long long i=2; i*i<=n; i++) if (n%i==0) return false;
    return true;
}

// Sàng Eratosthenes: O(N log log N)
vector<bool> sieve(int n) {
    vector<bool> p(n+1,true); p[0]=p[1]=false;
    for (int i=2; i*i<=n; i++) if (p[i]) for (int j=i*i; j<=n; j+=i) p[j]=false;
    return p;
}

def is_prime(n):
    if n < 2: return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0: return False
    return True

#include <numeric>
int g = gcd(a, b);
int l = lcm(a, b);

from math import gcd
g = gcd(a, b)
l = a * b // gcd(a, b)

const long long MOD = 1e9+7;
(a+b)%MOD
(a-b+MOD)%MOD
a*b%MOD

// Lũy thừa nhanh O(log n)
long long power(long long a, long long n, long long mod) {
    long long res=1; a%=mod;
    while (n>0) { if (n&1) res=res*a%mod; a=a*a%mod; n>>=1; }
    return res;
}

// Nghịch đảo modulo (mod nguyên tố)
long long inv(long long a) { return power(a, MOD-2, MOD); }

pow(a, n, mod)  # lũy thừa nhanh built-in

const int MAXN=1e6+5;
long long fact[MAXN], inv_fact[MAXN];
void precompute() {
    fact[0]=1;
    for (int i=1; i<MAXN; i++) fact[i]=fact[i-1]*i%MOD;
    inv_fact[MAXN-1]=power(fact[MAXN-1],MOD-2,MOD);
    for (int i=MAXN-2; i>=0; i--) inv_fact[i]=inv_fact[i+1]*(i+1)%MOD;
}
long long C(int n,int k) {
    if (k<0||k>n) return 0;
    return fact[n]*inv_fact[k]%MOD*inv_fact[n-k]%MOD;
}

from math import comb
print(comb(10, 3))  # C(10,3) = 120

map<int,int> factorize(int n) {
    map<int,int> f;
    for (int i=2; i*i<=n; i++) while (n%i==0) { f[i]++; n/=i; }
    if (n>1) f[n]++;
    return f;
}

long long ext_gcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// Phương trình ax ≡ c (mod m) có nghiệm khi gcd(a,m) | c
long long solve_linear(long long a, long long c, long long m) {
    long long x, y;
    long long g = ext_gcd(a, m, x, y);
    if (c % g != 0) return -1;
    long long mod = m / g;
    return (x % mod * (c / g) % mod + mod) % mod;
}

pair<long long, long long> crt(long long r1, long long m1, long long r2, long long m2) {
    long long x, y;
    long long g = ext_gcd(m1, m2, x, y);
    long long lcm = m1 / g * m2;
    long long ans = (r1 + m1 * ((r2 - r1) % m2 * x % m2 + m2)) % lcm;
    return {ans, lcm};
}

// Hợp nhiều phương trình:
long long r = 0, m = 1;
for (auto [ri, mi] : equations) {
    auto [new_r, new_m] = crt(r, m, ri, mi);
    r = new_r; m = new_m;
}