結果
| 問題 |
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;
}