50uint64_t
power(uint64_t a, uint64_t b, uint64_t c) {
59 ans = ((ans % c) * (a % c)) % c;
63 a = ((a % c) * (a % c)) % c;
76 uint64_t inverse =
power(b, p - 2, p) % p;
78 ((a % p) * (inverse % p)) % p;
91 assert(test_case_1 == 0);
92 std::cout <<
"Test 1 Passed!" << std::endl;
94 assert(test_case_2 == 5);
95 std::cout <<
"Test 2 Passed!" << std::endl;
97 assert(test_case_3 == 0);
98 std::cout <<
"Test 3 Passed!" << std::endl;
100 assert(test_case_4 == 2);
101 std::cout <<
"Test 4 Passed!" << std::endl;
103 assert(test_case_5 == 2);
104 std::cout <<
"Test 5 Passed!" << std::endl;
113int main(
int argc,
char *argv[]) {
uint64_t power(uint64_t a, uint64_t b, uint64_t c)
This function calculates a raised to exponent b under modulo c using modular exponentiation.
uint64_t mod_division(uint64_t a, uint64_t b, uint64_t p)
This function calculates modular division.
Functions for Modular Division implementation.