結果
問題 |
No.8123 Calculated N !
|
ユーザー |
👑 |
提出日時 | 2025-04-01 23:12:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,679 ms / 2,000 ms |
コード長 | 10,894 bytes |
コンパイル時間 | 5,864 ms |
コンパイル使用メモリ | 333,348 KB |
実行使用メモリ | 7,328 KB |
最終ジャッジ日時 | 2025-04-01 23:13:13 |
合計ジャッジ時間 | 22,703 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 16 |
ソースコード
#line 1 "yukicoder/play/535/i.cpp" #ifdef ONLINE_JUDGE #include <bits/stdc++.h> #include <atcoder/all> #else #include <precompile.h> #endif using namespace std; using ll=long long; using namespace atcoder; using mint=modint1000000007; #define rep1(i, r) for(int i=0; i<(int)(r); ++i) #define rep2(i, l, r) for(int i=(l); i<(int)(r); ++i) #define rep3(i, l, r, d) for(int i=(l); i<(int)(r); i+=(d)) #define rep_r1(i, r) for(int i=(r)-1; i>=0; --i) #define rep_r2(i, l, r) for(int i=(r)-1; i>=(l); --i) #define rep_r3(i, l, r, d) for(int i=(r)-1; i>=(l); i-=(d)) #define fifth(a, b, c, d, e, ...) e #define rep(...) fifth(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define rep_r(...) fifth(__VA_ARGS__, rep_r3, rep_r2, rep_r1)(__VA_ARGS__) template <typename... T> void in(T &... args) { (cin >> ... >> args); } template <typename... T> void in_z(T &... args) { (cin >> ... >> args); (..., --args); } #define in_d(type, ...) type __VA_ARGS__; in(__VA_ARGS__) #define in_dz(type, ...) type __VA_ARGS__; in_z(__VA_ARGS__) template <typename It> void in_i(It first, It last) { for(It it=first;it!=last;++it){ in(*it); } } template <typename It> void in_iz(It first, It last) { for(It it=first;it!=last;++it){ in(*it); --*it; } } template <int N> struct str_literal { static constexpr int length=N-1; char buf[N]; constexpr str_literal(const char (&s_literal)[N]){ rep(i, N){ buf[i]=s_literal[i]; } buf[length]='\0'; } }; template <int N> ostream & operator<<(ostream & os, const str_literal<N> & str) { os << str.buf; return os; } template <str_literal tail="\n", bool do_flush=false> void out() { cout << tail; if(do_flush){ cout << flush; } } template <str_literal split=" ", str_literal tail="\n", bool do_flush=false, typename Hd, typename... Tl> void out(const Hd & hd, const Tl &... tl) { cout << hd; if constexpr (sizeof...(Tl)){ (cout << ... << (cout << split, tl)); } cout << tail; if(do_flush){ cout << flush; } } template <str_literal split=" ", str_literal tail="\n", bool do_flush=false, typename It> void out_i(It first, It last) { for(It it=first;it!=last;++it){ if(it!=first){ cout << split; } cout << *it; } cout << tail; if(do_flush){ cout << flush; } } template <str_literal tail="\n", bool do_flush=false> void err() { cerr << tail; if(do_flush){ cout << flush; } } template <str_literal split=" ", str_literal tail="\n", bool do_flush=false, typename Hd, typename... Tl> void err(const Hd & hd, const Tl &... tl) { cerr << hd; if constexpr (sizeof...(Tl)){ (cerr << ... << (cerr << split, tl)); } cerr << tail; if(do_flush){ cout << flush; } } template <str_literal split=" ", str_literal tail="\n", bool do_flush=false, typename It> void err_i(It first, It last) { for(It it=first;it!=last;++it){ if(it!=first){ cerr << split; } cerr << *it; } cerr << tail; if(do_flush){ cout << flush; } } #define dir(dx, dy) for(auto [dx, dy]: {pair{1, 0}, {0, 1}, {-1, 0}, {0, -1}}) #define dir_8(dx, dy) for(auto [dx, dy]: {pair{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}}) #define all(v) (v).begin(), (v).end() #define all_r(v) (v).rbegin(), (v).rend() #define dedup(v) (v).erase(unique(all(v)), (v).end()) #define yn(b) ((b) ? "Yes" : "No") template <typename T1, typename T2> bool chmin(T1 & l, const T2 & r) { if(r<l){ l=r; return true; } return false; } template <typename T1, typename T2> bool chmax(T1 & l, const T2 & r) { if(r>l){ l=r; return true; } return false; } template <typename Hd1, typename Hd2, typename... Tl> auto min_of(Hd1 hd1, Hd2 hd2, Tl... tl) { if constexpr (sizeof...(Tl)==0){ return min(hd1, hd2); } else { return min(hd1, min_of(hd2, tl...)); } } template <typename Hd1, typename Hd2, typename... Tl> auto max_of(Hd1 hd1, Hd2 hd2, Tl... tl) { if constexpr (sizeof...(Tl)==0){ return max(hd1, hd2); } else { return max(hd1, max_of(hd2, tl...)); } } template <typename Hd1, typename Hd2, typename... Tl> auto gcd_of(Hd1 hd1, Hd2 hd2, Tl... tl) { if constexpr (sizeof...(Tl)==0){ return gcd(hd1, hd2); } else { return gcd(hd1, gcd_of(hd2, tl...)); } } template <typename Hd1, typename Hd2, typename... Tl> auto lcm_of(Hd1 hd1, Hd2 hd2, Tl... tl) { if constexpr (sizeof...(Tl)==0){ return lcm(hd1, hd2); } else { return lcm(hd1, lcm_of(hd2, tl...)); } } template <typename T, size_t N> auto make_vector(vector<size_t> & sizes, T const& x) { if constexpr (N==1){ return vector(sizes[0], x); } else { size_t size=sizes[N-1]; sizes.pop_back(); return vector(size, make_vector<T, N-1>(sizes, x)); } } template <typename T, size_t N> auto make_vector(size_t const(&sizes)[N], T const& x=T()) { vector<size_t> s(N); rep(i, N){ s[i] = sizes[N-i-1]; } return make_vector<T, N>(s, x); } template <typename T, size_t N> auto make_vector(vector<int> & sizes, T const& x) { if constexpr (N==1){ return vector(sizes[0], x); } else { int size=sizes[N-1]; sizes.pop_back(); return vector(size, make_vector<T, N-1>(sizes, x)); } } template <typename T, size_t N> auto make_vector(int const(&sizes)[N], T const& x=T()) { vector<int> s(N); rep(i, N){ s[i] = sizes[N-i-1]; } return make_vector<T, N>(s, x); } template <typename T, size_t Hd, size_t... Tl> auto make_array() { if constexpr (sizeof...(Tl)==0){ return array<T, Hd>{}; } else { return array<decltype(make_array<T, Tl...>()), Hd>{}; } } constexpr int inf32=1'000'000'001; constexpr ll inf64=2'000'000'000'000'000'001; constexpr ll ten_powers[19]={ 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000, 1000000000000000, 10000000000000000, 100000000000000000, 1000000000000000000 }; template <typename S, S e> constexpr S e_const() { return e; } template <typename S1, S1 e1, typename S2, S2 e2> constexpr pair<S1, S2> e_pair() { return {e1, e2}; } template <typename S> S op_min(S a, S b) { return min(a, b); } template <typename S> S op_max(S a, S b) { return max(a, b); } template <typename S> S op_add(S a, S b) { return a+b; } template <typename S1, typename S2> pair<S1, S2> op_add_pair(pair<S1, S2> a, pair<S1, S2> b) { auto [a1, a2]=a; auto [b1, b2]=b; return {a1+b1, a2+b2}; } template <typename F1, typename F2, typename S> S mapping_affine(pair<F1, F2> f, S x) { auto [a, b]=f; return a*x+b; } template <typename F1, typename F2, typename S1, typename S2> pair<S1, S2> mapping_len_and_affine(pair<F1, F2> f, pair<S1, S2> x) { auto [a, b]=f; auto [x1, x2]=x; return {x1, a*x2+b*x1}; } template <typename F1, typename F2> pair<F1, F2> composition_affine(pair<F1, F2> f, pair<F1, F2> g) { auto [a_f, b_f]=f; auto [a_g, b_g]=g; return {a_f*a_g, a_f*b_g+b_f}; } #line 1 "/opt/ei1333_s_library/math/number-theory/prime-table.hpp" /** * @brief Prime Table(素数テーブル) * */ vector<bool> prime_table(int n) { vector<bool> prime(n + 1, true); if (n >= 0) prime[0] = false; if (n >= 1) prime[1] = false; for (int i = 2; i * i <= n; i++) { if (!prime[i]) continue; for (int j = i * i; j <= n; j += i) { prime[j] = false; } } return prime; } #line 2 "/opt/ei1333_s_library/math/number-theory/enumerate-primes.hpp" vector<int> enumerate_primes(int n) { if (n <= 1) return {}; auto d = prime_table(n); vector<int> primes; primes.reserve(count(begin(d), end(d), true)); for (int i = 0; i < d.size(); i++) { if (d[i]) primes.push_back(i); } return primes; } #line 291 "yukicoder/play/535/i.cpp" // #include "math/number-theory/prime-count.hpp" #line 1 "/opt/ei1333_s_library/math/number-theory/kth-root-integer.hpp" uint64_t kth_root_integer(uint64_t a, int k) { if (k == 1) return a; auto check = [&](uint32_t x) { uint64_t mul = 1; for (int j = 0; j < k; j++) { if (__builtin_mul_overflow(mul, x, &mul)) return false; } return mul <= a; }; uint64_t ret = 0; for (int i = 31; i >= 0; i--) { if (check(ret | (1u << i))) ret |= 1u << i; } return ret; } #line 294 "yukicoder/play/535/i.cpp" /** * @brief Prime Count(素数の個数) */ template <int64_t LIM = 100000000000LL> struct PrimeCount { private: int64_t sq; vector<bool> prime; vector<int64_t> prime_sum, primes; int64_t p2(int64_t x, int64_t y) { if (x < 4) return 0; int64_t a = pi(y); int64_t b = pi(kth_root_integer(x, 2)); if (a >= b) return 0; int64_t sum = (a - 2) * (a + 1) / 2 - (b - 2) * (b + 1) / 2; for (int64_t i = a; i < b; i++) sum += pi(x / primes[i]); return sum; } int64_t phi(int64_t m, int64_t n) { if (m < 1) return 0; if (n > m) return 1; if (n < 1) return m; if (m <= primes[n - 1] * primes[n - 1]) return pi(m) - n + 1; if (m <= primes[n - 1] * primes[n - 1] * primes[n - 1] && m <= sq) { int64_t sx = pi(kth_root_integer(m, 2)); int64_t ans = pi(m) - (sx + n - 2) * (sx - n + 1) / 2; for (int64_t i = n; i < sx; ++i) ans += pi(m / primes[i]); return ans; } return phi(m, n - 1) - phi(m / primes[n - 1], n - 1); } public: PrimeCount() : sq(kth_root_integer(LIM, 2)), prime_sum(sq + 1) { prime = prime_table(sq); for (int i = 1; i <= sq; i++) prime_sum[i] = prime_sum[i - 1] + prime[i]; primes.reserve(prime_sum[sq]); for (int i = 1; i <= sq; i++) if (prime[i]) primes.push_back(i); } int64_t pi(int64_t n) { if (n <= sq) return prime_sum[n]; int64_t m = kth_root_integer(n, 3); int64_t a = pi(m); return phi(n, a) + a - 1 - p2(n, m); } }; uint64_t uint64_floor_sqrt(uint64_t n) { if (n == 0) return 0; uint64_t tmp_m1 = std::sqrt(n) - 1; return tmp_m1 * (tmp_m1 + 2) < n ? tmp_m1 + 1 : tmp_m1; } int main(void) { cout << fixed << setprecision(15); cerr << fixed << setprecision(15); in_d(ll, n); ll sqrt_n=uint64_floor_sqrt(n); auto primes=enumerate_primes(sqrt_n); mint ans=1; for(auto p: primes){ mint b=1; ll p_pow=p; while(p_pow<=n){ b+=n/p_pow; p_pow*=p; } ans*=b; } PrimeCount<> pc; for(ll q=1;q<=sqrt_n;++q){ ll r=n/q; ll l=n/(q+1); ans*=mint(q+1).pow(pc.pi(r)-pc.pi(max(l, sqrt_n))); } out(ans.val()); return 0; }