結果
問題 | No.502 階乗を計算するだけ |
ユーザー |
![]() |
提出日時 | 2017-04-08 11:49:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 710 ms / 1,000 ms |
コード長 | 1,338 bytes |
コンパイル時間 | 638 ms |
コンパイル使用メモリ | 56,784 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-17 23:39:12 |
合計ジャッジ時間 | 5,359 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 52 |
ソースコード
#include <cstdio>#include <vector>#include <algorithm>#include <cassert>using namespace std;using i64 = long long;int pow_mod(int b, int e, int mod) {int ret = 1;for (; e; e >>= 1, b = i64(b) * b % mod) {if (e & 1) ret = i64(ret) * b % mod;}return ret;}int fact_valuation(int n, int p) {int ret = n /= p;while (n >= p) {n /= p;ret += n;}return ret;}template <int p>int fact_mod(i64 n) {if (n >= p) return 0;if (n * 2 > p) {int ret = fact_mod<p>(p - n - 1);ret = (p - n - 1) & 1 ? ret : p - ret;return pow_mod(ret, p - 2, p);}vector<int> ns;for (int i = n; i > 1; i /= 5)for (int j = i; j > 1; j /= 3)for (int k = j; k > 1; k >>= 1)ns.push_back(k);std::sort(ns.begin(), ns.end());const int d[8] = {6, 4, 2, 4, 2, 4, 6, 2};int ret = 1, prod = 1, i = 1, r = 0;for (auto end : ns) {for (; i <= end; i += d[r & 7], ++r) {prod = i64(prod) * i % p;}ret = i64(ret) * prod % p;}ret = i64(ret) * pow_mod(2, fact_valuation(n, 2), p) % p;ret = i64(ret) * pow_mod(3, fact_valuation(n, 3), p) % p;ret = i64(ret) * pow_mod(5, fact_valuation(n, 5), p) % p;return ret;}int main() {const int mod = 1e9 + 7;i64 N;while (~scanf("%lld", &N)) {printf("%d\n", fact_mod<mod>(N));}}