結果
問題 |
No.8123 Calculated N !
|
ユーザー |
|
提出日時 | 2025-03-28 20:50:42 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 303 ms / 2,000 ms |
コード長 | 1,365 bytes |
コンパイル時間 | 3,423 ms |
コンパイル使用メモリ | 282,392 KB |
実行使用メモリ | 11,000 KB |
最終ジャッジ日時 | 2025-04-01 20:50:21 |
合計ジャッジ時間 | 6,993 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 16 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/modint> using mint = atcoder::modint1000000007; using ll = long long; using vl = vector<ll>; ll floor_sqrt(ll n) { ll l = 0, r = 1e9; while (r - l > 1) { ll x = (l + r) / 2; (x * x <= n ? l : r) = x; } return l; } pair<vl, vl> prime_count(ll n) { ll sq = floor_sqrt(n); vl large(sq + 1, 0), small(n / sq, 0); for (ll i = 1; i < large.size(); i++) large[i] = n / i - 1; for (ll i = 1; i < small.size(); i++) small[i] = i - 1; for (ll p = 2; p <= sq; p++) { if (p < small.size()) { if (small[p] <= small[p - 1]) continue; } else { if (large[n / p] <= small[p - 1]) continue; } ll pc = small[p - 1], q = p * p; for (ll i = 1; i <= sq && n / i >= q; i++) { ll ip = i * p; (i <= sq ? large[i] : small[n / i]) -= (ip <= sq ? large[ip] : small[n / ip]) - pc; } for (ll i = n / sq - 1; i >= q; i--) small[i] -= small[i / p] - pc; } vl x, c; for (ll i = 1; i < small.size(); i++) { x.push_back(i); c.push_back(small[i]); } for (ll i = sq; i; i--) { x.push_back(n / i); c.push_back(large[i]); } return {x, c}; } int main() { ll n; cin >> n; auto [x, c] = prime_count(n); mint ans = 1; for (int i = 1; i < x.size(); i++) { mint s = 1; for (ll v = n; v;) s += v /= x[i]; ans *= s.pow(c[i] - c[i - 1]); } cout << ans.val() << "\n"; }