結果

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

ソースコード

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