結果

問題 No.8123 Calculated N !
コンテスト
ユーザー KumaTachiRen
提出日時 2025-04-01 14:29:33
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,232 bytes
コンパイル時間 4,062 ms
コンパイル使用メモリ 281,284 KB
実行使用メモリ 19,120 KB
最終ジャッジ日時 2025-04-01 20:51:29
合計ジャッジ時間 8,011 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5 TLE * 1
other -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}

vl eratosthenes_sieve(ll n) {
	vector<bool> f(n + 1, true);
	vl ps;
	ll p = 2;
	for (ll p = 2; p * p <= n; p++) {
		if (!f[p]) continue;
		for (ll q = p * p; q <= n; q += p) f[q] = false;
	}
	for (; p <= n; p++) if (f[p]) ps.push_back(p);
	return ps;
}

int main() {
	ll n;
	cin >> n;
	mint ans = 1;
	const int W = 1000000;
	ll sq0 = floor_sqrt(n);
	vl ps = eratosthenes_sieve(sq0);
	for (auto p : ps) {
		mint v = 1;
		for (ll x = n; x;) v += x /= p;
		ans *= v;
	}
	for (ll l = sq0 + 1; l <= n; l += W) {
		ll r = min(n, l + W - 1);
		ll d = r - l + 1;
		ll sq = floor_sqrt(r);
		vl lpf(d, 0);
		for (auto p : ps) {
			if (p > sq) break;
			for (ll j = max(2ll, (l + p - 1) / p * p); j <= r; j += p)
				if (lpf[j - l] == 0) lpf[j - l] = p;
		}
		for (ll i = 0; i < d; i++)
			if (lpf[i] == 0 && i + l > 1) {
				ll p = lpf[i] = i + l;
				mint v = 1;
				for (ll x = n; x; ) v += x /= p;
				ans *= v;
			}
	}
	cout << ans.val() << "\n";
}
0