結果

問題 No.8123 Calculated N !
ユーザー KumaTachiRen
提出日時 2025-03-30 13:38:39
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,027 bytes
コンパイル時間 3,167 ms
コンパイル使用メモリ 279,456 KB
実行使用メモリ 10,916 KB
最終ジャッジ日時 2025-04-01 20:51:15
合計ジャッジ時間 9,723 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 15 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
	int m = nsq + sq;
	
	vl f(m, 0);
	for (ll i = 1; i <= sq; i++) f[m - 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] == 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[m - i] -= f[ip <= sq ? m - 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 *= helper(n, i).pow(cnt - prv);
		prv = cnt;
	}
	for (ll i = sq; i; i--) {
		ll cnt = f[m - i];
		ans *= helper(n, n / i).pow(cnt - prv);
		prv = cnt;
	}
	cout << ans.val() << "\n";
}
0