結果
問題 | No.1532 Different Products |
ユーザー | KoD |
提出日時 | 2021-06-04 21:18:51 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 3,947 ms / 4,000 ms |
コード長 | 3,118 bytes |
コンパイル時間 | 2,488 ms |
コンパイル使用メモリ | 213,972 KB |
実行使用メモリ | 212,352 KB |
最終ジャッジ日時 | 2024-04-30 01:24:34 |
合計ジャッジ時間 | 146,101 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 9 ms
11,136 KB |
testcase_01 | AC | 1,180 ms
81,328 KB |
testcase_02 | AC | 9 ms
11,392 KB |
testcase_03 | AC | 8 ms
11,136 KB |
testcase_04 | AC | 9 ms
11,264 KB |
testcase_05 | AC | 9 ms
11,264 KB |
testcase_06 | AC | 9 ms
11,520 KB |
testcase_07 | AC | 9 ms
11,264 KB |
testcase_08 | AC | 10 ms
11,628 KB |
testcase_09 | AC | 88 ms
28,568 KB |
testcase_10 | AC | 2,060 ms
113,700 KB |
testcase_11 | AC | 1,172 ms
83,548 KB |
testcase_12 | AC | 2,708 ms
130,328 KB |
testcase_13 | AC | 2,571 ms
131,644 KB |
testcase_14 | AC | 3,250 ms
135,420 KB |
testcase_15 | AC | 10 ms
11,508 KB |
testcase_16 | AC | 868 ms
75,324 KB |
testcase_17 | AC | 1,178 ms
84,060 KB |
testcase_18 | AC | 247 ms
58,060 KB |
testcase_19 | AC | 2,947 ms
133,296 KB |
testcase_20 | AC | 3,367 ms
139,880 KB |
testcase_21 | AC | 1,324 ms
82,084 KB |
testcase_22 | AC | 2,596 ms
128,056 KB |
testcase_23 | AC | 595 ms
75,192 KB |
testcase_24 | AC | 3,240 ms
137,064 KB |
testcase_25 | AC | 2,330 ms
119,172 KB |
testcase_26 | AC | 162 ms
34,808 KB |
testcase_27 | AC | 1,550 ms
87,408 KB |
testcase_28 | AC | 1,576 ms
89,328 KB |
testcase_29 | AC | 818 ms
73,396 KB |
testcase_30 | AC | 2,025 ms
110,712 KB |
testcase_31 | AC | 2,008 ms
112,608 KB |
testcase_32 | AC | 2,429 ms
118,052 KB |
testcase_33 | AC | 1,889 ms
109,320 KB |
testcase_34 | AC | 2,825 ms
130,232 KB |
testcase_35 | AC | 2,403 ms
118,440 KB |
testcase_36 | AC | 2,747 ms
126,068 KB |
testcase_37 | AC | 312 ms
48,524 KB |
testcase_38 | AC | 2,980 ms
131,248 KB |
testcase_39 | AC | 2,637 ms
125,660 KB |
testcase_40 | AC | 2,698 ms
127,080 KB |
testcase_41 | AC | 3,843 ms
211,484 KB |
testcase_42 | AC | 3,320 ms
138,836 KB |
testcase_43 | AC | 3,411 ms
141,888 KB |
testcase_44 | AC | 3,803 ms
211,248 KB |
testcase_45 | AC | 3,822 ms
211,412 KB |
testcase_46 | AC | 3,483 ms
143,768 KB |
testcase_47 | AC | 3,896 ms
211,968 KB |
testcase_48 | AC | 3,821 ms
211,192 KB |
testcase_49 | AC | 3,819 ms
211,676 KB |
testcase_50 | AC | 3,823 ms
211,204 KB |
testcase_51 | AC | 3,831 ms
211,756 KB |
testcase_52 | AC | 3,789 ms
210,408 KB |
testcase_53 | AC | 3,911 ms
212,004 KB |
testcase_54 | AC | 3,815 ms
210,664 KB |
testcase_55 | AC | 3,839 ms
211,572 KB |
testcase_56 | AC | 3,468 ms
143,704 KB |
testcase_57 | AC | 3,660 ms
209,864 KB |
testcase_58 | AC | 3,833 ms
211,016 KB |
testcase_59 | AC | 3,429 ms
141,824 KB |
testcase_60 | AC | 3,947 ms
212,352 KB |
testcase_61 | AC | 9 ms
11,136 KB |
testcase_62 | AC | 9 ms
11,264 KB |
testcase_63 | AC | 3,875 ms
211,536 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; }