結果

問題 No.8123 Calculated N !
ユーザー KumaTachiRen
提出日時 2025-03-30 13:53:19
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 288 ms / 2,000 ms
コード長 1,055 bytes
コンパイル時間 3,218 ms
コンパイル使用メモリ 277,788 KB
実行使用メモリ 7,328 KB
最終ジャッジ日時 2025-04-01 20:51:22
合計ジャッジ時間 6,821 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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>;

mint helper(ll n, ll x, ll k) {
	if (k == 0) return 1;
	mint v = 1;
	while (n) v += n /= x;
	return v.pow(k);
}

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