#line 1 "main.cpp" #include #line 2 "/home/user/GitHub/competitive-programming-library/utils/macros.hpp" #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) std::begin(x), std::end(x) #line 3 "/home/user/GitHub/competitive-programming-library/data_structure/union_find_tree.hpp" /** * @brief Union-Find Tree * @docs data_structure/union_find_tree.md * @note union-by-size + path-compression */ struct union_find_tree { std::vector data; union_find_tree() = default; explicit union_find_tree(std::size_t n) : data(n, -1) {} bool is_root(int i) { return data[i] < 0; } int find_root(int i) { return is_root(i) ? i : (data[i] = find_root(data[i])); } int tree_size(int i) { return - data[find_root(i)]; } int unite_trees(int i, int j) { i = find_root(i); j = find_root(j); if (i != j) { if (tree_size(i) < tree_size(j)) std::swap(i, j); data[i] += data[j]; data[j] = i; } return i; } bool is_same(int i, int j) { return find_root(i) == find_root(j); } }; #line 8 "/home/user/GitHub/competitive-programming-library/graph/kruskal.hpp" /** * @brief minimum spanning tree / 最小全域木 (Kruskal's method) * @note $O(E \log E)$ * @note it becomes a forest if the given graph is not connected * @return a list of indices of edges */ template std::vector compute_minimum_spanning_tree(int n, std::vector > edges) { std::vector order(edges.size()); std::iota(ALL(order), 0); std::sort(ALL(order), [&](int i, int j) { return std::make_pair(std::get<2>(edges[i]), i) < std::make_pair(std::get<2>(edges[j]), j); }); std::vector tree; union_find_tree uft(n); for (int i : order) { int x = std::get<0>(edges[i]); int y = std::get<1>(edges[i]); if (not uft.is_same(x, y)) { uft.unite_trees(x, y); tree.push_back(i); } } return tree; } #line 4 "main.cpp" using namespace std; int64_t solve(int l, int r) { // [l, r) vector > edges; auto use = [&](int i, int j) { edges.emplace_back(i - l, j - l, min(i % j, j % i)); }; REP3 (i, l, r) { REP3 (j, i + 1, min(100, 2 * i)) if (j < r) { use(i, j); } for (int j = 2 * i; j < r; j += i) { REP (k, min(4, i)) if (j + k < r) { use(i, j + k); } } } int64_t ans = 0; vector used = compute_minimum_spanning_tree(r - l, edges); for (int i : used) { ans += get<2>(edges[i]); } return ans; } // generated by online-judge-template-generator v4.1.0 (https://github.com/kmyk/online-judge-template-generator) int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); constexpr char endl = '\n'; int64_t L, R; cin >> L >> R; ++ R; auto ans = solve(L, R); cout << ans << endl; return 0; }