Project_euler/700.cpp at master · nhanlun/Project_euler · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <queue>
#include <set>

long long mul(long long a, long long b, long long mod) {
  if (b == 1) {
    return a % mod;
  }
  auto tmp = mul(a, b / 2, mod);
  return b & 1 ? (tmp * 2 + a) % mod : (tmp * 2) % mod;
}

int main() {
  long long n = 1504170715041707LL;
  long long base = 1504170715041707LL;
  long long MOD = 4503599627370517LL;
  // std::set<long long> m;
  // m.insert(n);
  // long long sum = n;
  // long long Min = n;
  // while (true) {
  //   n = (n + base) % MOD;
  //   if (m.find(n) == m.end()) {
  //     m.insert(n);
  //   } else {
  //     break;
  //   }
  //   if (n < Min) {
  //     Min = n;
  //     sum += n;
  //     std::cout << n << ' ' << Min << ' ' << sum << ' ' << m.size() <<
  //     std::endl;
  //   }
  //   if (Min < 1) {
  //     break;
  //   }
  //   if (m.size() % 1000000 == 0) {
  //     std::cout << n << ' ' << Min << ' ' << sum << ' ' << m.size() <<
  //     std::endl;
  //   }
  //   // std::cout << n << ' ' << Min << ' ' << sum << ' ' << m.size() <<
  //   std::endl;
  // }

  // 15806432 1517926220024813
  // modulo inverse = 3451657199285664
  long long inverse = 3451657199285664LL;
  long long cur = inverse;
  long long sum = 1517926220024813LL;
  for (long long i = 2; i < 15806432LL; ++i) {
    auto pos = mul(inverse, i, MOD);
    if (pos < cur) {
      std::cout << i << ' ' << pos << ' ' << cur << ' ' << sum << std::endl;
      cur = pos;
      sum += i;
    }
  }
  std::cout << sum + 1 << std::endl;
  return 0;
}