結果

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

ソースコード

diff # 

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