結果

問題 No.8123 Calculated N !
コンテスト
ユーザー KumaTachiRen
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

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";
}
0