結果
| 問題 | No.2365 Present of good number |
| ユーザー |
 ebi_fly
|
| 提出日時 | 2023-07-01 00:59:48 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 215 ms / 2,000 ms |
| コード長 | 8,794 bytes |
| コンパイル時間 | 1,822 ms |
| コンパイル使用メモリ | 154,112 KB |
| 実行使用メモリ | 9,192 KB |
| 最終ジャッジ日時 | 2023-09-21 18:37:11 |
| 合計ジャッジ時間 | 12,465 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 212 ms
9,180 KB |
| testcase_01 | AC | 213 ms
9,172 KB |
| testcase_02 | AC | 211 ms
9,076 KB |
| testcase_03 | AC | 211 ms
9,060 KB |
| testcase_04 | AC | 212 ms
9,068 KB |
| testcase_05 | AC | 212 ms
9,124 KB |
| testcase_06 | AC | 211 ms
9,132 KB |
| testcase_07 | AC | 212 ms
9,168 KB |
| testcase_08 | AC | 213 ms
9,124 KB |
| testcase_09 | AC | 212 ms
9,124 KB |
| testcase_10 | AC | 211 ms
9,068 KB |
| testcase_11 | AC | 212 ms
9,064 KB |
| testcase_12 | AC | 212 ms
9,172 KB |
| testcase_13 | AC | 213 ms
9,172 KB |
| testcase_14 | AC | 212 ms
9,176 KB |
| testcase_15 | AC | 215 ms
9,060 KB |
| testcase_16 | AC | 215 ms
9,056 KB |
| testcase_17 | AC | 211 ms
9,192 KB |
| testcase_18 | AC | 212 ms
9,120 KB |
| testcase_19 | AC | 214 ms
9,056 KB |
| testcase_20 | AC | 212 ms
9,168 KB |
| testcase_21 | AC | 212 ms
9,176 KB |
| testcase_22 | AC | 211 ms
9,120 KB |
| testcase_23 | AC | 210 ms
9,064 KB |
| testcase_24 | AC | 212 ms
9,120 KB |
| testcase_25 | AC | 213 ms
9,176 KB |
| testcase_26 | AC | 212 ms
9,056 KB |
| testcase_27 | AC | 210 ms
9,064 KB |
| testcase_28 | AC | 211 ms
9,072 KB |
| testcase_29 | AC | 212 ms
9,172 KB |
| testcase_30 | AC | 212 ms
9,188 KB |
| testcase_31 | AC | 211 ms
9,068 KB |
| testcase_32 | AC | 210 ms
9,112 KB |
| testcase_33 | AC | 212 ms
9,180 KB |
| testcase_34 | AC | 211 ms
9,052 KB |
| testcase_35 | AC | 212 ms
9,180 KB |
| testcase_36 | AC | 211 ms
9,112 KB |
| testcase_37 | AC | 210 ms
9,060 KB |
| testcase_38 | AC | 211 ms
9,112 KB |
| testcase_39 | AC | 211 ms
9,060 KB |
| testcase_40 | AC | 210 ms
9,180 KB |
ソースコード
#line 1 "a.cpp"
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
/* macro */
#define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++)
#define rrep(i, a, n) for (int i = ((int)(n)-1); i >= (int)(a); i--)
#define Rep(i, a, n) for (i64 i = (i64)(a); i < (i64)(n); i++)
#define RRep(i, a, n) for (i64 i = ((i64)(n)-i64(1)); i >= (i64)(a); i--)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
/* macro end */
/* template */
namespace ebi {
#ifdef LOCAL
#define debug(...) \
std::cerr << "LINE: " << __LINE__ << " [" << #__VA_ARGS__ << "]:", \
debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
void debug_out() {
std::cerr << std::endl;
}
template <typename Head, typename... Tail> void debug_out(Head h, Tail... t) {
std::cerr << " " << h;
if (sizeof...(t) > 0) std::cerr << " :";
debug_out(t...);
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &pa) {
return os << pa.first << " " << pa.second;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &os, std::pair<T1, T2> &pa) {
return os >> pa.first >> pa.second;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &vec) {
for (std::size_t i = 0; i < vec.size(); i++)
os << vec[i] << (i + 1 == vec.size() ? "" : " ");
return os;
}
template <typename T>
std::istream &operator>>(std::istream &os, std::vector<T> &vec) {
for (T &e : vec) std::cin >> e;
return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::optional<T> &opt) {
if (opt) {
os << opt.value();
} else {
os << "invalid value";
}
return os;
}
using std::size_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
template <class T> inline bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T> inline bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <class T> T pow(T x, i64 n) {
T res = 1;
while (n > 0) {
if (n & 1) res = res * x;
x = x * x;
n >>= 1;
}
return res;
}
template <class T> struct Edge {
int to;
T cost;
Edge(int _to, T _cost = 1) : to(_to), cost(_cost) {}
};
template <class T> struct Graph : std::vector<std::vector<Edge<T>>> {
using std::vector<std::vector<Edge<T>>>::vector;
void add_edge(int u, int v, T w, bool directed = false) {
(*this)[u].emplace_back(v, w);
if (directed) return;
(*this)[v].emplace_back(u, w);
}
};
struct graph : std::vector<std::vector<int>> {
using std::vector<std::vector<int>>::vector;
void add_edge(int u, int v, bool directed = false) {
(*this)[u].emplace_back(v);
if (directed) return;
(*this)[v].emplace_back(u);
}
};
constexpr i64 LNF = std::numeric_limits<i64>::max() / 4;
constexpr int INF = std::numeric_limits<int>::max() / 2;
const std::vector<int> dy = {1, 0, -1, 0, 1, 1, -1, -1};
const std::vector<int> dx = {0, 1, 0, -1, 1, -1, 1, -1};
} // namespace ebi
#line 2 "math/linear_sieve.hpp"
#line 2 "utility/int_alias.hpp"
#line 5 "utility/int_alias.hpp"
using std::size_t;
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using u16 = std::uint16_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
#line 4 "math/linear_sieve.hpp"
/*
reference: https://37zigen.com/linear-sieve/
verify: https://atcoder.jp/contests/abc162/submissions/25095562
*/
#line 11 "math/linear_sieve.hpp"
namespace ebi {
struct linear_sieve {
private:
using u64 = std::uint64_t;
int n;
std::vector<int> sieve;
std::vector<int> prime;
public:
linear_sieve(int _n) : n(_n), sieve(std::vector<int>(_n + 1, -1)) {
for (int i = 2; i <= n; i++) {
if (sieve[i] < 0) {
sieve[i] = i;
prime.emplace_back(i);
}
for (auto p : prime) {
if (u64(p) * u64(i) > u64(n) || p > sieve[i]) break;
sieve[p * i] = p;
}
}
}
std::vector<int> prime_table() {
return prime;
}
std::vector<std::pair<int, int>> factorize(int n) {
std::vector<std::pair<int, int>> res;
while (n > 1) {
int p = sieve[n];
int exp = 0;
if (p < 0) {
res.emplace_back(n, 1);
break;
}
while (sieve[n] == p) {
n /= p;
exp++;
}
res.emplace_back(p, exp);
}
return res;
}
std::vector<int> divisors(int n) {
std::vector<int> res;
res.emplace_back(1);
auto pf = factorize(n);
for (auto p : pf) {
int sz = res.size();
for (int i = 0; i < sz; i++) {
int ret = 1;
for (int j = 0; j < p.second; j++) {
ret *= p.first;
res.emplace_back(res[i] * ret);
}
}
}
return res;
}
template <class T> std::vector<T> fast_zeta(const std::vector<T> &f) {
std::vector<T> F = f;
int sz = f.size();
assert(sz <= n + 1);
for (int i = 2; i < sz; i++) {
if (sieve[i] != i) continue;
for (int j = (sz - 1) / i; j >= 1; j--) {
F[j] += F[j * i];
}
}
return F;
}
template <class T> std::vector<T> fast_mobius(const std::vector<T> &F) {
std::vector<T> f = F;
int sz = F.size();
assert(sz <= n + 1);
for (int i = 2; i < sz; i++) {
if (sieve[i] != i) continue;
for (int j = 1; j * i < sz; j++) {
f[j] -= f[j * i];
}
}
return f;
}
template <class modint> std::vector<modint> pow_table(int k) {
std::vector<modint> table(n + 1, 1);
table[0] = 0;
for (int i = 2; i <= n; i++) {
if (sieve[i] == i) {
table[i] = modint(i).pow(k);
continue;
}
table[i] = table[sieve[i]] * table[i / sieve[i]];
}
return table;
}
template <class modint> std::vector<modint> inv_table() {
return pow_table(modint::mod() - 2);
}
};
} // namespace ebi
#line 166 "a.cpp"
#include <atcoder/modint>
namespace ebi {
using mint = atcoder::modint1000000007;
using dmint = atcoder::dynamic_modint<0>;
void main_() {
int n;
i64 k;
std::cin >> n >> k;
int max = 200000;
linear_sieve sieve(max);
auto ptable = sieve.prime_table();
int sz = ptable.size();
std::vector<int> inv_ptable(max, -1);
rep(i,0,sz) inv_ptable[ptable[i]] = i;
dmint::set_mod(mint::mod() - 1);
std::vector a(60, std::vector<dmint>(sz));
for(auto [p, c]: sieve.factorize(n)) a[0][inv_ptable[p]] = c;
rep(i,0,60-1) {
rep(j,0,sz) {
for(auto [p,c]: sieve.factorize(ptable[j] + 1)) {
a[i+1][inv_ptable[p]] += c * a[i][j];
}
}
}
if(k < 60) {
mint ans = 1;
rep(i,0,sz) ans *= mint(ptable[i]).pow(a[k][i].val());
std::cout << ans.val() << '\n';
}
else {
k -= 59;
std::vector<dmint> res(2);
res[0] = a[59][0] * dmint(2).pow(k >> 1);
res[1] = a[59][1] * dmint(2).pow(k >> 1);
if(k & 1) {
std::swap(res[0], res[1]);
res[0] *= 2;
}
mint ans = mint(2).pow(res[0].val()) * mint(3).pow(res[1].val());
std::cout << ans.val() << '\n';
}
}
} // namespace ebi
int main() {
std::cout << std::fixed << std::setprecision(15);
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
int t = 1;
// std::cin >> t;
while (t--) {
ebi::main_();
}
return 0;
}