Modular Arithmetic Basics

1
#include <iostream>
2
#include <cstdint>
3
4
// Normalize a into the range [0, m-1]
5
long long norm(long long a, long long m) {
6
    long long r = a % m;          // In C++, this can be negative if a < 0
7
    if (r < 0) r += m;            // Ensure nonnegative representative
8
    return r;
9
}
10
11
// (a + b) mod m, avoiding overflow
12
long long add_mod(long long a, long long b, long long m) {
13
    long long x = norm(a, m);
14
    long long y = norm(b, m);
15
    long long s = x + y;
16
    if (s >= m) s -= m;           // Equivalent to (x + y) % m but faster and avoids extra modulo
17
    return s;
18
}
19
20
// (a - b) mod m, return in [0, m-1]
21
long long sub_mod(long long a, long long b, long long m) {
22
    long long x = norm(a, m);
23
    long long y = norm(b, m);
24
    long long d = x - y;
25
    if (d < 0) d += m;            // Normalize after subtraction
26
    return d;
27
}
28
29
// (a * b) mod m using 128-bit to avoid overflow (GCC/Clang extension)
30
long long mul_mod(long long a, long long b, long long m) {
31
    __int128 x = (__int128)norm(a, m) * (__int128)norm(b, m);
32
    return (long long)(x % m);
33
}
34
35
int main() {
36
    long long a = -17, b = 25, m = 1000000007LL; // Example values
37
38
    std::cout << "a mod m = " << norm(a, m) << "\n";      // Expect m-17
39
    std::cout << "b mod m = " << norm(b, m) << "\n";
40
41
    std::cout << "(a + b) mod m = " << add_mod(a, b, m) << "\n";
42
    std::cout << "(a - b) mod m = " << sub_mod(a, b, m) << "\n";
43
    std::cout << "(a * b) mod m = " << mul_mod(a, b, m) << "\n";
44
45
    // Demonstrate large multiplication safety
46
    long long x = 1000000000000000000LL; // 1e18
47
    long long y = 1000000000000000000LL; // 1e18
48
    long long mm = 1000000007LL;
49
    std::cout << "(1e18 * 1e18) mod 1e9+7 = " << mul_mod(x, y, mm) << "\n";
50
51
    return 0;
52
}
53

1
#include <iostream>
2
#include <tuple>
3
#include <cstdint>
4
5
long long norm(long long a, long long m) {
6
    long long r = a % m; if (r < 0) r += m; return r;
7
}
8
9
long long mul_mod(long long a, long long b, long long m) {
10
    __int128 x = (__int128)norm(a, m) * (__int128)norm(b, m);
11
    return (long long)(x % m);
12
}
13
14
// a^e mod m using binary exponentiation
15
long long pow_mod(long long a, long long e, long long m) {
16
    long long base = norm(a, m);
17
    long long res = 1 % m;
18
    while (e > 0) {
19
        if (e & 1) res = mul_mod(res, base, m);
20
        base = mul_mod(base, base, m);
21
        e >>= 1;
22
    }
23
    return res;
24
}
25
26
// Extended Euclidean Algorithm: returns (g, x, y) such that ax + by = g = gcd(a, b)
27
std::tuple<long long, long long, long long> ext_gcd(long long a, long long b) {
28
    if (b == 0) return {a >= 0 ? a : -a, a >= 0 ? 1 : -1, 0};
29
    auto [g, x1, y1] = ext_gcd(b, a % b);
30
    long long x = y1;
31
    long long y = x1 - (a / b) * y1;
32
    return {g, x, y};
33
}
34
35
// Modular inverse via Extended Euclid; returns (exists, inverse)
36
std::pair<bool, long long> inv_mod_euclid(long long a, long long m) {
37
    auto [g, x, y] = ext_gcd(a, m);
38
    if (g != 1 && g != -1) return {false, 0};
39
    long long inv = norm(x, m);
40
    return {true, inv};
41
}
42
43
// Modular inverse via Fermat's little theorem; m must be prime and gcd(a, m) = 1
44
long long inv_mod_fermat(long long a, long long m_prime) {
45
    return pow_mod(a, m_prime - 2, m_prime);
46
}
47
48
int main() {
49
    const long long P = 1000000007LL; // prime modulus
50
51
    // Fast power example
52
    std::cout << "2^1000 mod P = " << pow_mod(2, 1000, P) << "\n";
53
54
    // Inverse via Fermat (valid since P is prime and 3 != 0 mod P)
55
    std::cout << "inv(3) mod P = " << inv_mod_fermat(3, P) << "\n";
56
    // Check: 3 * inv(3) mod P == 1
57
    std::cout << "check: 3 * inv(3) % P = " << ( ( (__int128)3 * inv_mod_fermat(3, P) ) % P ) << "\n";
58
59
    // Inverse via Extended Euclid under composite modulus
60
    long long a = 7, m = 26; // gcd(7,26)=1, inverse exists
61
    auto [ok1, inv1] = inv_mod_euclid(a, m);
62
    std::cout << "inv(7) mod 26 exists? " << (ok1 ? "yes" : "no") << ", value = " << (ok1 ? inv1 : -1) << "\n";
63
64
    // Non-invertible example: gcd(6,15)=3 != 1
65
    auto [ok2, inv2] = inv_mod_euclid(6, 15);
66
    std::cout << "inv(6) mod 15 exists? " << (ok2 ? "yes" : "no") << "\n";
67
68
    return 0;
69
}
70

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Normalize to [0, m-1]
5
static inline long long norm(long long a, long long m) {
6
    long long r = a % m; if (r < 0) r += m; return r;
7
}
8
9
// Returns true if there exists a non-empty subarray with sum % m == 0
10
bool has_divisible_subarray(const vector<long long>& a, long long m) {
11
    unordered_set<long long> seen;
12
    long long prefix = 0;
13
    seen.insert(0); // prefix sum 0 at position -1 ensures single-prefix divisible case is captured
14
    for (long long x : a) {
15
        prefix = norm(prefix + norm(x, m), m);
16
        if (seen.count(prefix)) return true; // two equal prefix sums modulo m imply subarray divisible by m
17
        seen.insert(prefix);
18
    }
19
    return false;
20
}
21
22
int main() {
23
    vector<long long> arr = {5, -2, 3, 1, -4, 6};
24
    long long m = 7;
25
26
    cout << boolalpha;
27
    cout << "Has subarray with sum divisible by " << m << "? " << has_divisible_subarray(arr, m) << "\n";
28
29
    // As an extra, compute the total sum and product modulo m safely
30
    long long sum = 0, prod = 1 % m;
31
    for (long long x : arr) {
32
        sum = (sum + norm(x, m)) % m;
33
        __int128 t = (__int128)prod * norm(x, m);
34
        prod = (long long)(t % m);
35
    }
36
    cout << "sum(arr) mod m = " << sum << "\n";
37
    cout << "product(arr) mod m = " << prod << "\n";
38
39
    return 0;
40
}
41

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Extended Euclidean: returns (g, x, y) with ax + by = g = gcd(a, b)
5
tuple<long long, long long, long long> ext_gcd(long long a, long long b) {
6
    if (b == 0) return {a >= 0 ? a : -a, a >= 0 ? 1 : -1, 0};
7
    auto [g, x1, y1] = ext_gcd(b, a % b);
8
    long long x = y1;
9
    long long y = x1 - (a / b) * y1;
10
    return {g, x, y};
11
}
12
13
long long norm(long long a, long long m) { long long r = a % m; if (r < 0) r += m; return r; }
14
15
// Solve ax ≡ b (mod m). Returns all solutions in [0, m-1].
16
vector<long long> solve_linear_congruence(long long a, long long b, long long m) {
17
    auto [g, x, y] = ext_gcd(a, m);
18
    if (b % g != 0) return {}; // no solutions
19
    // Reduce to coprime case
20
    long long a1 = a / g, b1 = b / g, m1 = m / g;
21
    // x is inverse of a1 modulo m1
22
    long long inv_a1 = norm(x, m1);
23
    long long x0 = ( (__int128)inv_a1 * (b1 % m1 + m1) ) % m1; // base solution modulo m1
24
    // All solutions: x = x0 + k*m1 for k = 0..g-1
25
    vector<long long> sols;
26
    sols.reserve((size_t)g);
27
    for (long long k = 0; k < g; ++k) {
28
        long long sol = x0 + k * m1;
29
        sol = norm(sol, m); // ensure in [0, m-1]
30
        sols.push_back(sol);
31
    }
32
    sort(sols.begin(), sols.end());
33
    sols.erase(unique(sols.begin(), sols.end()), sols.end());
34
    return sols;
35
}
36
37
int main() {
38
    // Example 1: 14x ≡ 30 (mod 100)
39
    long long a = 14, b = 30, m = 100;
40
    auto sols1 = solve_linear_congruence(a, b, m);
41
    cout << "Solving " << a << "x ≡ " << b << " (mod " << m << ")\n";
42
    if (sols1.empty()) cout << "No solution\n";
43
    else {
44
        cout << "Solutions (" << sols1.size() << "): ";
45
        for (auto v : sols1) cout << v << ' ';
46
        cout << "\n";
47
    }
48
49
    // Example 2: No-solution case: 6x ≡ 5 (mod 15), since gcd(6,15)=3 ∤ 5
50
    a = 6; b = 5; m = 15;
51
    auto sols2 = solve_linear_congruence(a, b, m);
52
    cout << "Solving " << a << "x ≡ " << b << " (mod " << m << ")\n";
53
    if (sols2.empty()) cout << "No solution\n";
54
55
    return 0;
56
}
57