ulvis.paste.net

Paste Search Dynamic
Recent pastes
uint64_t
  1. #include <inttypes.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <stdint.h>
  5.  
  6. uint64_t summod(uint64_t a, uint64_t b, uint64_t c) {
  7.     a %= c;
  8.     b %= c;
  9.     if (a + b >= a) {
  10.         return (a + b) % c;
  11.     } else {
  12.         return (a - (c - b));
  13.     }
  14. }
  15.  
  16. uint64_t mulmod(uint64_t a, uint64_t b, uint64_t c) {
  17.     if (a == 0 || b == 0)
  18.         return 0;
  19.     if (a % 2 == 0) {
  20.         uint64_t buf = mulmod(a / 2, b, c);
  21.         return summod(buf, buf, c);
  22.     } else {
  23.         uint64_t buf = mulmod(a - 1, b, c);
  24.         return summod(buf, b, c);
  25.     }
  26. }
  27.  
  28. int main() {
  29.     uint64_t a, b, c;
  30.     scanf("%" SCNu64 "%" SCNu64 "%" SCNu64, &a, &b, &c);
  31.     printf("%" PRIu64 "\n", mulmod(a, b, c));
  32.  
  33.     return 0;
  34. }
  35.  
Parsed in 0.005 seconds