#include <iostream>
#include <cstdint>
/*
================================================================
Modulo Multiplication (Slow and Fast Versions)
================================================================
Goal:
Compute (a * b) % mod safely for large 64‑bit values
without using BigInteger.
Why two versions?
1. Slow version:
- Conceptually simple.
- Adds 'b' to the result 'a' times.
- Always correct, but extremely slow for large numbers.
- Useful as a "ground truth" reference.
2. Fast version:
- Uses the classic "double‑and‑add" technique.
- Runs in O(log b) time.
- Must use __uint128_t internally to avoid overflow.
- Produces the same correct result as the slow version.
================================================================
*/
// ---------------------------------------------------------------
// SLOW VERSION (always correct, but very slow)
// ---------------------------------------------------------------
std::uint64_t mul_mod_slow(std::uint64_t a, std::uint64_t b, std::uint64_t mod) {
/*
This version literally performs:
result = (b + b + b + ... a times) % mod
It never overflows because:
- result stays below mod
- b fits in uint64_t
- addition is safe
But it is O(a), which is far too slow for large inputs.
*/
if (b < a)
std::swap(a, b); // reduce number of loop iterations
std::uint64_t result = 0;
for (std::uint64_t i = 0; i < a; i++) {
result += b;
result %= mod;
}
return result;
}
// ---------------------------------------------------------------
// FAST VERSION (efficient and safe using __uint128_t)
// ---------------------------------------------------------------
std::uint64_t mul_mod_fast(std::uint64_t a, std::uint64_t b, std::uint64_t mod) {
/*
This version uses the "double‑and‑add" method:
- If the lowest bit of b is set, add 'a' to result.
- Double 'a' each step.
- Shift b right each step.
The key improvement:
Use __uint128_t for intermediate values so that
doubling 'a' never overflows.
This makes the algorithm:
- Fast: O(log b)
- Safe: no overflow
- Exact: matches slow version
*/
__uint128_t A = a;
__uint128_t B = b;
__uint128_t M = mod;
__uint128_t result = 0;
while (B > 0) {
if (B & 1)
result = (result + A) % M;
A = (A << 1) % M;
B >>= 1;
}
return static_cast<std::uint64_t>(result);
}
// ---------------------------------------------------------------
// MAIN PROGRAM
// ---------------------------------------------------------------
int main() {
std::uint64_t x = 798345ULL;
std::uint64_t y = 20289473612815ULL;
std::uint64_t mod = 100000000000003ULL;
std::uint64_t slow_result = mul_mod_slow(x, y, mod);
std::uint64_t fast_result = mul_mod_fast(x, y, mod);
std::cout << "Slow result: " << slow_result << "\n";
std::cout << "Fast result: " << fast_result << "\n";
}
/*
run:
Slow result: 99811422305238
Fast result: 99811422305238
*/
