結果
問題 |
No.8123 Calculated N !
|
ユーザー |
👑 ![]() |
提出日時 | 2025-04-01 22:17:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 47 ms / 2,000 ms |
コード長 | 8,375 bytes |
コンパイル時間 | 1,280 ms |
コンパイル使用メモリ | 85,036 KB |
実行使用メモリ | 7,328 KB |
最終ジャッジ日時 | 2025-04-01 22:17:37 |
合計ジャッジ時間 | 2,545 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 16 |
ソースコード
#ifdef NACHIA #define _GLIBCXX_DEBUG #else #define NDEBUG #endif #include <iostream> #include <string> #include <vector> #include <algorithm> using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(i64 i=0; i<i64(n); i++) const i64 INF = 1001001001001001001; template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; } template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; } using namespace std; #include <utility> #include <cassert> namespace nachia{ namespace internal{ // mod 2^64 constexpr unsigned long long PowerOfULongLong(unsigned long long a, unsigned long long i){ unsigned long long res = 1; while(i){ if(i&1){ res *= a; } i /= 2; a *= a; } return res; } } unsigned long long FloorOfKthRoot(unsigned long long real, unsigned long long k){ using u64 = unsigned long long; assert(k != 0); if(real <= 1) return real; if(k >= 64) return 1; if(k == 1) return real; struct Precalc{ // a^i <= x static constexpr bool lesseq(u64 a, int i, u64 x) { if (a == 0) return true; for(int j=0; j<i; j++) x /= a; return x >= 1; } unsigned long long BORDER[64]; constexpr Precalc() : BORDER() { for (int idx = 2; idx <= 63; idx++) { u64 l = 0, r = 1ull << 33; while (l + 1 < r) { u64 m = (l + r) / 2; if (lesseq(m, idx, ~0ull)) l = m; else r = m; } BORDER[idx] = r; } }; }; constexpr Precalc precalc; u64 l = 0, r = precalc.BORDER[k]; if(real < r) r = real; while (l + 1 < r) { u64 m = (l + r) / 2; if(internal::PowerOfULongLong(m, k) <= real) l = m; else r = m; } return l; } unsigned long long CeilOfKthRoot(unsigned long long real, unsigned long long k){ if(real <= 1) return real; if(k >= 64) return 2; if(k == 1) return real; unsigned long long x = FloorOfKthRoot(real, k); if(internal::PowerOfULongLong(x, k) != real) x++; return x; } } // namespace nachia namespace nachia{ int Popcount(unsigned long long c) noexcept { #ifdef __GNUC__ return __builtin_popcountll(c); #else c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3)); c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5)); c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17)); c = (c * (~0ull/257)) >> 56; return c; #endif } // please ensure x != 0 int MsbIndex(unsigned long long x) noexcept { #ifdef __GNUC__ return 63 - __builtin_clzll(x); #else using u64 = unsigned long long; int q = (x >> 32) ? 32 : 0; auto m = x >> q; constexpr u64 hi = 0x88888888; constexpr u64 mi = 0x11111111; m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35; m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 31; q += (m & 0xf) << 2; q += 0x3333333322221100 >> (((x >> q) & 0xf) << 2) & 0xf; return q; #endif } // please ensure x != 0 int LsbIndex(unsigned long long x) noexcept { #ifdef __GNUC__ return __builtin_ctzll(x); #else return MsbIndex(x & -x); #endif } } namespace nachia{ std::pair<std::vector<long long>, std::vector<long long>> CountingPrimesTable(long long maxval) { struct Div2By1 { using u32 = unsigned int; using u64 = unsigned long long; int w; u32 d; u32 v; Div2By1(){} Div2By1(u32 m){ w = 31 - MsbIndex(m); d = m << w; v = (u32)((u64(-1) / d) - (u64(1) << 32)); } u32 operator()(u64 u) const { u <<= w; u32 u1 = u32(u >> 32); u32 q = u32((u64(1) * v * u1) >> 32) + u1; u -= u64(1) * q * d; if (u >= u64(2) * d){ u -= u64(2) * d; q += 2; } if (u >= d){ q += 1; } return q; } }; using i64 = long long; i64 N = maxval; if(N <= 1) return { {0,0}, {0,0} }; i64 Nr2 = FloorOfKthRoot(N, 2); i64 Nr4 = FloorOfKthRoot(Nr2, 2); i64 Dsz = N / (Nr2+1); i64 Asz = (Nr2+1) + Dsz; std::vector<i64> Div(Nr2+1); for(i64 i=1; i<=Nr2; i++) Div[i] = N / i; std::vector<i64> A(Asz + 1, 0); for(i64 i=1; i<=Nr2; i++) A[i] = i-1; for(i64 i=1; i<=Dsz; i++) A[Asz-i] = Div[i]-1; for(i64 p=2; p<=Nr4; p++) if(A[p] - A[p-1] != 0){ auto div2By1 = Div2By1(p); i64 i = 1; i64 small = A[p-1]; for( ; i*p<=Dsz; i++) A[Asz-i] -= A[Asz-i*p] - small; for( ; i<=Dsz; i++) A[Asz-i] -= A[div2By1(Div[i])] - small; i64 Nr2dp = div2By1(Nr2); for(i64 j=Nr2dp*p; j<=Nr2; j++) A[j] -= A[Nr2dp] - small; for(i64 j=Nr2dp-1; j>=p; j--) for(i64 t=0; t<p; t++) A[j*p+t] -= A[j] - small; } for(i64 p=Nr4+1; p<=Nr2; p++) if(A[p] - A[p-1] != 0){ auto div2By1 = Div2By1(p); i64 i = 1; i64 small = A[p-1]; i64 l = div2By1(Div[p]); for( ; i*p<=Dsz; i++) A[Asz-i] -= A[Asz-i*p] - small; for( ; i<=l; i++) A[Asz-i] -= A[div2By1(Div[i])] - small; } return std::make_pair( std::vector<i64>(A.begin(), A.begin() + (Nr2 + 1)), std::vector<i64>(A.rbegin(), A.rbegin() + (Dsz + 1)) ); } long long CountingPrimes(long long maxval){ return CountingPrimesTable(maxval).second[1]; } } // namespace nachia namespace nachia{ // ax + by = gcd(a,b) // return ( x, - ) std::pair<long long, long long> ExtGcd(long long a, long long b){ long long x = 1, y = 0; while(b){ long long u = a / b; std::swap(a-=b*u, b); std::swap(x-=y*u, y); } return std::make_pair(x, a); } } // namespace nachia namespace nachia{ template<unsigned int MOD> struct StaticModint{ private: using u64 = unsigned long long; unsigned int x; public: using my_type = StaticModint; template< class Elem > static Elem safe_mod(Elem x){ if(x < 0){ if(0 <= x+MOD) return x + MOD; return MOD - ((-(x+MOD)-1) % MOD + 1); } return x % MOD; } StaticModint() : x(0){} StaticModint(const my_type& a) : x(a.x){} StaticModint& operator=(const my_type&) = default; template< class Elem > StaticModint(Elem v) : x(safe_mod(v)){} unsigned int operator*() const { return x; } my_type& operator+=(const my_type& r) { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; } my_type operator+(const my_type& r) const { my_type res = *this; return res += r; } my_type& operator-=(const my_type& r) { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; } my_type operator-(const my_type& r) const { my_type res = *this; return res -= r; } my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; } my_type& operator*=(const my_type& r){ x = (u64)x * r.x % MOD; return *this; } my_type operator*(const my_type& r) const { my_type res = *this; return res *= r; } bool operator==(const my_type& r) const { return x == r.x; } my_type pow(unsigned long long i) const { my_type a = *this, res = 1; while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; } return res; } my_type inv() const { return my_type(ExtGcd(x, MOD).first); } unsigned int val() const { return x; } int hval() const { return int(x > MOD/2 ? x - MOD : x); } static constexpr unsigned int mod() { return MOD; } static my_type raw(unsigned int val) { auto res = my_type(); res.x = val; return res; } my_type& operator/=(const my_type& r){ return operator*=(r.inv()); } my_type operator/(const my_type& r) const { return operator*(r.inv()); } }; } // namespace nachia using Modint = nachia::StaticModint<1000000007>; void testcase(){ i64 N; cin >> N; auto [A,B] = nachia::CountingPrimesTable(N); Modint ans = 1; for(i64 i=2; i<i64(A.size()); i++) if(A[i] - A[i-1]){ i64 cnt = 0; for(i64 n=N/i; n; n/=i) cnt += n; ans *= cnt + 1; } for(i64 i=1; i+1<i64(B.size()); i++) B[i] -= B[i+1]; B.back() -= A.back(); for(i64 d=1; d<i64(B.size()); d++){ ans *= Modint(d+1).pow(B[d]); } cout << ans.val() << "\n"; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); testcase(); return 0; }