fork download
copy 
  1. #include <iostream>
  2. #include <cassert>
  3. using namespace std;
  4.  
  5. int multiply(int a, int b, int mod) {
  6.     if (b == 0) {
  7.         // a * 0 = 0
  8.         return 0;
  9.     } else {
  10.         // b = 2k + r
  11.         int k = b / 2;
  12.         int r = b % 2;
  13.  
  14.         // a * (2k + r) = 2a * k + a * r
  15.         return (multiply(a * 2 % mod, k, mod) + a * r) % mod;
  16.     }
  17. }
  18.  
  19. void test(int a, int b) {
  20.     int mod = 1e9 + 7;
  21.     int result = multiply(a, b, mod);
  22.     int expected = a * (long long) b % mod;
  23.     assert(result == expected);
  24.     cout << result << " " << expected << endl;
  25. }
  26.  
  27. int main() {
  28.     srand(time(nullptr));
  29.     test(3, 5);
  30.     test(5, 3);
  31.     test(100, 100);
  32.     test(777, 77777);
  33.     test(50000, 50000);
  34.     test(100000, 100000);
  35. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
15 15
15 15
10000 10000
60432729 60432729
499999986 499999986
999999937 999999937
https://ideone.com/ZwkV98
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!