test/atcoder/abc179_c.enum_quo.test.cpp

View this file on GitHub
Last update: 2025-08-08 01:11:39+09:00
Problem: https://atcoder.jp/contests/abc179/tasks/abc179_c

Depends on

$\lfloor N/i \rfloor$ の列挙 (src/NumberTheory/enumerate_quotients.hpp)

Code

// competitive-verifier: IGNORE
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc179/tasks/abc179_c
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
// O(√N)
#include <iostream>
#include "src/NumberTheory/enumerate_quotients.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 long long ans= 0;
 for (auto [q, l, r]: enumerate_quotients(N - 1)) ans+= (r - l) * q;
 cout << ans << '\n';
 return 0;
}

#line 1 "test/atcoder/abc179_c.enum_quo.test.cpp"
// competitive-verifier: IGNORE
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc179/tasks/abc179_c
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
// O(√N)
#include <iostream>
#line 2 "src/NumberTheory/enumerate_quotients.hpp"
#include <vector>
#include <algorithm>
#include <tuple>
#include <cmath>
#include <cstdint>
// (q,l,r) : i in (l,r], ⌊N/i⌋ = q
std::vector<std::tuple<uint64_t, uint64_t, uint64_t>> enumerate_quotients(uint64_t N) {
 uint64_t sq= std::sqrt(N), prev= N, x;
 std::vector<std::tuple<uint64_t, uint64_t, uint64_t>> ret;
 for (int q= 1, n= (sq * sq + sq <= N ? sq : sq - 1); q <= n; ++q) ret.emplace_back(q, x= double(N) / (q + 1), prev), prev= x;
 for (int l= sq; l >= 1; --l) ret.emplace_back(double(N) / l, l - 1, l);
 return ret;
}
#line 8 "test/atcoder/abc179_c.enum_quo.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 long long ans= 0;
 for (auto [q, l, r]: enumerate_quotients(N - 1)) ans+= (r - l) * q;
 cout << ans << '\n';
 return 0;
}