結果
問題 |
No.1383 Numbers of Product
|
ユーザー |
|
提出日時 | 2021-02-07 21:14:41 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,383 bytes |
コンパイル時間 | 3,583 ms |
コンパイル使用メモリ | 100,784 KB |
最終ジャッジ日時 | 2025-01-18 14:21:32 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 TLE * 3 |
ソースコード
#line 1 "main.cpp" #include <iostream> #include <map> using namespace std; using lint = long long; constexpr lint INF = 1LL << 60; lint prod(lint a, lint b) { if (a == 0 || b == 0) return 0; if (a >= INF / b + 1) return INF; return min(INF, a * b); } void solve() { lint n, k, m; cin >> n >> k >> m; auto g = [&](lint a, lint b) { auto ret = a; for (lint x = 1; x <= b; ++x) { ret = prod(ret, a + prod(k, x)); } return ret; }; map<lint, int> cnt; for (lint b = 2; b <= 18; ++b) { for (lint a = 1;; ++a) { auto p = g(a, b); if (p > n) break; if (!cnt.count(p)) cnt[p] = 0; ++cnt[p]; } } auto h = [&](lint x) { lint ok = 0, ng = INF; while (ng - ok > 1) { lint a = (ok + ng) / 2; if (g(a, 1) <= x) { ok = a; } else { ng = a; } } return ok; }; lint ones = h(n); for (auto& [x, c] : cnt) { if (g(h(x), 1) == x) { ++c; --ones; } } lint ans = (m == 1 ? ones : 0); for (auto [x, c] : cnt) { if (c == m) ++ans; } cout << ans << "\n"; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); solve(); return 0; }