結果
問題 |
No.8123 Calculated N !
|
ユーザー |
|
提出日時 | 2025-03-29 11:55:44 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,063 bytes |
コンパイル時間 | 3,450 ms |
コンパイル使用メモリ | 277,756 KB |
実行使用メモリ | 16,072 KB |
最終ジャッジ日時 | 2025-04-01 20:51:09 |
合計ジャッジ時間 | 10,505 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 15 TLE * 1 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/modint> using mint = atcoder::modint1000000007; using ll = long long; using vl = vector<ll>; mint helper(ll n, ll x) { mint v = 1; while (n) v += n /= x; return v; } int main() { ll n; cin >> n; ll sq = 1; while (sq * sq <= n) sq++; sq--; ll nsq = n / sq; vl f(1 + nsq + sq, 0); for (ll i = 1; i <= sq; i++) f[nsq + i] = n / i - 1; for (ll i = 1; i < nsq; i++) f[i] = i - 1; for (ll p = 2; p <= sq; p++) { if (f[p < nsq ? p : nsq + n / p] <= f[p - 1]) continue; ll q = f[p - 1], pp = p * p; for (ll i = 1; i <= sq && n / i >= pp; i++) { ll ip = i * p; f[nsq + i] -= f[ip <= sq ? nsq + ip : n / ip] - q; } for (ll i = n / sq - 1; i >= pp; i--) f[i] -= f[i / p] - q; } mint ans = 1; ll prv = f[1]; for (ll i = 2; i < nsq; i++) { ll cnt = f[i]; ans *= mint(helper(n, i)).pow(cnt - prv); prv = cnt; } for (ll i = sq; i; i--) { ll cnt = f[nsq + i]; ans *= mint(helper(n, n / i)).pow(cnt - prv); prv = cnt; } cout << ans.val() << "\n"; }