結果
問題 | No.1532 Different Products |
ユーザー | KoD |
提出日時 | 2021-06-04 21:18:51 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,689 ms / 4,000 ms |
コード長 | 3,118 bytes |
コンパイル時間 | 5,682 ms |
コンパイル使用メモリ | 211,760 KB |
実行使用メモリ | 215,556 KB |
最終ジャッジ日時 | 2023-08-12 11:23:09 |
合計ジャッジ時間 | 99,976 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
11,228 KB |
testcase_01 | AC | 891 ms
83,532 KB |
testcase_02 | AC | 5 ms
11,336 KB |
testcase_03 | AC | 5 ms
11,152 KB |
testcase_04 | AC | 5 ms
11,184 KB |
testcase_05 | AC | 5 ms
11,328 KB |
testcase_06 | AC | 5 ms
11,220 KB |
testcase_07 | AC | 6 ms
11,392 KB |
testcase_08 | AC | 8 ms
11,468 KB |
testcase_09 | AC | 73 ms
28,764 KB |
testcase_10 | AC | 1,412 ms
115,676 KB |
testcase_11 | AC | 836 ms
85,620 KB |
testcase_12 | AC | 1,786 ms
130,808 KB |
testcase_13 | AC | 1,643 ms
133,036 KB |
testcase_14 | AC | 2,103 ms
136,636 KB |
testcase_15 | AC | 6 ms
11,296 KB |
testcase_16 | AC | 694 ms
76,612 KB |
testcase_17 | AC | 851 ms
84,416 KB |
testcase_18 | AC | 226 ms
57,876 KB |
testcase_19 | AC | 2,072 ms
133,664 KB |
testcase_20 | AC | 2,170 ms
141,696 KB |
testcase_21 | AC | 939 ms
83,728 KB |
testcase_22 | AC | 1,713 ms
128,508 KB |
testcase_23 | AC | 431 ms
75,812 KB |
testcase_24 | AC | 2,116 ms
139,188 KB |
testcase_25 | AC | 1,676 ms
120,452 KB |
testcase_26 | AC | 138 ms
34,652 KB |
testcase_27 | AC | 1,112 ms
89,172 KB |
testcase_28 | AC | 1,164 ms
93,104 KB |
testcase_29 | AC | 706 ms
75,112 KB |
testcase_30 | AC | 1,414 ms
112,148 KB |
testcase_31 | AC | 1,415 ms
114,656 KB |
testcase_32 | AC | 1,637 ms
118,428 KB |
testcase_33 | AC | 1,385 ms
111,104 KB |
testcase_34 | AC | 1,929 ms
130,932 KB |
testcase_35 | AC | 1,649 ms
120,320 KB |
testcase_36 | AC | 1,819 ms
126,508 KB |
testcase_37 | AC | 283 ms
50,324 KB |
testcase_38 | AC | 1,987 ms
133,508 KB |
testcase_39 | AC | 1,785 ms
126,848 KB |
testcase_40 | AC | 1,795 ms
129,188 KB |
testcase_41 | AC | 2,479 ms
213,808 KB |
testcase_42 | AC | 2,184 ms
140,964 KB |
testcase_43 | AC | 2,490 ms
143,620 KB |
testcase_44 | AC | 2,483 ms
213,056 KB |
testcase_45 | AC | 2,482 ms
213,188 KB |
testcase_46 | AC | 2,315 ms
144,660 KB |
testcase_47 | AC | 2,689 ms
215,380 KB |
testcase_48 | AC | 2,459 ms
213,056 KB |
testcase_49 | AC | 2,473 ms
213,872 KB |
testcase_50 | AC | 2,450 ms
212,592 KB |
testcase_51 | AC | 2,469 ms
213,960 KB |
testcase_52 | AC | 2,447 ms
211,424 KB |
testcase_53 | AC | 2,498 ms
213,420 KB |
testcase_54 | AC | 2,428 ms
212,164 KB |
testcase_55 | AC | 2,465 ms
213,240 KB |
testcase_56 | AC | 2,405 ms
145,124 KB |
testcase_57 | AC | 2,476 ms
211,328 KB |
testcase_58 | AC | 2,595 ms
212,956 KB |
testcase_59 | AC | 2,238 ms
143,228 KB |
testcase_60 | AC | 2,526 ms
215,556 KB |
testcase_61 | AC | 5 ms
11,352 KB |
testcase_62 | AC | 5 ms
11,228 KB |
testcase_63 | AC | 2,610 ms
212,904 KB |
ソースコード
#include <bits/stdc++.h> using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; using i128 = __int128_t; using u128 = __uint128_t; using isize = std::ptrdiff_t; using usize = std::size_t; class rep { struct Iter { usize itr; constexpr Iter(const usize pos) noexcept : itr(pos) {} constexpr void operator++() noexcept { ++itr; } constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; } constexpr usize operator*() const noexcept { return itr; } }; const Iter first, last; public: explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {} constexpr Iter begin() const noexcept { return first; } constexpr Iter end() const noexcept { return last; } }; template <class F> struct RecursiveLambda : private F { explicit constexpr RecursiveLambda(F&& f) : F(std::forward<F>(f)) {} template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const { return F::operator()(*this, std::forward<Args>(args)...); } }; template <class F> constexpr decltype(auto) rec_lambda(F&& f) { using G = std::decay_t<F>; return RecursiveLambda<G>(std::forward<G>(f)); } template <class T> using Vec = std::vector<T>; void main_() { usize N; u64 K; std::cin >> N >> K; Vec<std::pair<u64, u64>> dp; dp.emplace_back(1, 1); for (const auto i : rep(1, std::min<usize>(N, 80) + 1)) { const auto cur = dp.size(); for (const auto j : rep(0, cur)) { if (dp[j].first * i <= K) { dp.emplace_back(dp[j].first * i, dp[j].second); } } std::inplace_merge(dp.begin(), dp.begin() + cur, dp.end()); Vec<std::pair<u64, u64>> next; u64 last = 0; for (const auto [x, c] : dp) { if (x != last) { next.emplace_back(x, 0); last = x; } next.back().second += c; } dp = std::move(next); } const auto size = dp.size(); Vec<u64> sum(size + 1); for (const auto i : rep(0, size)) { sum[i + 1] = sum[i] + dp[i].second; } std::array<u64, 1000000> count{}; for (const auto i : rep(0, size)) { if (dp[i].first <= 1000000) { count[dp[i].first] += dp[i].second; } } for (const auto i : rep(1, count.size())) { count[i] += count[i - 1]; } u64 ans = 0; rec_lambda([&](auto&& dfs, const u64 from, const u64 cur) -> void { if (cur > 10000) { ans += count[K / cur]; } else { ans += sum[std::lower_bound(dp.begin(), dp.end(), std::pair<u64, u64>(K / cur + 1, 0)) - dp.begin()]; } for (const auto next : rep(from, N + 1)) { if (cur * next > K) break; dfs(next + 1, cur * next); } })(81, 1); std::cout << ans - 1 << '\n'; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); main_(); return 0; }