/** * date : 2020-12-19 02:12:42 */ #define NDEBUG using namespace std; // intrinstic #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // utility namespace Nyaan { using ll = long long; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; template using V = vector; template using VV = vector>; using vi = vector; using vl = vector; using vd = V; using vs = V; using vvi = vector>; using vvl = vector>; template struct P : pair { template P(Args... args) : pair(args...) {} using pair::first; using pair::second; T &x() { return first; } const T &x() const { return first; } U &y() { return second; } const U &y() const { return second; } P &operator+=(const P &r) { first += r.first; second += r.second; return *this; } P &operator-=(const P &r) { first -= r.first; second -= r.second; return *this; } P &operator*=(const P &r) { first *= r.first; second *= r.second; return *this; } P operator+(const P &r) const { return P(*this) += r; } P operator-(const P &r) const { return P(*this) -= r; } P operator*(const P &r) const { return P(*this) *= r; } }; using pl = P; using pi = P; using vp = V; constexpr int inf = 1001001001; constexpr long long infLL = 4004004004004004004LL; template int sz(const T &t) { return t.size(); } template void mem(T (&a)[N], int c) { memset(a, c, sizeof(T) * N); } template inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template int lb(const vector &v, const T &a) { return lower_bound(begin(v), end(v), a) - begin(v); } template int ub(const vector &v, const T &a) { return upper_bound(begin(v), end(v), a) - begin(v); } constexpr long long TEN(int n) { long long ret = 1, x = 10; for (; n; x *= x, n >>= 1) ret *= (n & 1 ? x : 1); return ret; } template pair mkp(const T &t, const U &u) { return make_pair(t, u); } template vector mkrui(const vector &v, bool rev = false) { vector ret(v.size() + 1); if (rev) { for (int i = int(v.size()) - 1; i >= 0; i--) ret[i] = v[i] + ret[i + 1]; } else { for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i]; } return ret; }; template vector mkuni(const vector &v) { vector ret(v); sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } template vector mkord(int N, F f) { vector ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), f); return ord; } template vector reord(const vector &v, const vector &ord) { int N = v.size(); vector ret(N); for (int i = 0; i < N; i++) ret[i] = v[ord[i]]; return ret; }; template vector mkiota(int N) { vector ret(N); iota(begin(ret), end(ret), 0); return ret; } template vector mkinv(vector &v, int max_val = -1) { if (max_val < (int)v.size()) max_val = v.size() - 1; vector inv(max_val + 1, -1); for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i; return inv; } } // namespace Nyaan // bit operation namespace Nyaan { __attribute__((target("popcnt"))) inline int popcnt(const u64 &a) { return _mm_popcnt_u64(a); } __attribute__((target("bmi"))) inline int lsb(const u64 &a) { return _tzcnt_u64(a); } __attribute__((target("bmi"))) inline int ctz(const u64 &a) { return _tzcnt_u64(a); } __attribute__((target("lzcnt"))) inline int msb(const u64 &a) { return 63 - _lzcnt_u64(a); } __attribute__((target("lzcnt"))) inline int clz64(const u64 &a) { return _lzcnt_u64(a); } template inline int gbit(const T &a, int i) { return (a >> i) & 1; } template inline void sbit(T &a, int i, bool b) { a ^= (gbit(a, i) == b ? 0 : (T(b) << i)); } constexpr long long PW(int n) { return 1LL << n; } constexpr long long MSK(int n) { return (1LL << n) - 1; } } // namespace Nyaan // inout namespace Nyaan { template ostream &operator<<(ostream &os, const pair &p) { os << p.first << " " << p.second; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template istream &operator>>(istream &is, vector &v) { for (auto &x : v) is >> x; return is; } void in() {} template void in(T &t, U &... u) { cin >> t; in(u...); } void out() { cout << "\n"; } template void out(const T &t, const U &... u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } void outr() {} template void outr(const T &t, const U &... u) { cout << t; outr(u...); } struct IoSetupNya { IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7); } } iosetupnya; } // namespace Nyaan // debug namespace DebugImpl { template struct is_specialize : false_type {}; template struct is_specialize< U, typename conditional::type> : true_type {}; template struct is_specialize< U, typename conditional::type> : true_type {}; template struct is_specialize::value, void>> : true_type { }; void dump(const char& t) { cerr << t; } void dump(const string& t) { cerr << t; } template ::value, nullptr_t> = nullptr> void dump(const U& t) { cerr << t; } template void dump(const T& t, enable_if_t::value>* = nullptr) { string res; if (t == Nyaan::inf) res = "inf"; if (is_signed::value) if (t == -Nyaan::inf) res = "-inf"; if (sizeof(T) == 8) { if (t == Nyaan::infLL) res = "inf"; if (is_signed::value) if (t == -Nyaan::infLL) res = "-inf"; } if (res.empty()) res = to_string(t); cerr << res; } template void dump(const pair&); template void dump(const pair&); template void dump(const T& t, enable_if_t::value>* = nullptr) { cerr << "[ "; for (auto it = t.begin(); it != t.end();) { dump(*it); cerr << (++it == t.end() ? "" : ", "); } cerr << " ]"; } template void dump(const pair& t) { cerr << "( "; dump(t.first); cerr << ", "; dump(t.second); cerr << " )"; } template void dump(const pair& t) { cerr << "[ "; for (int i = 0; i < t.second; i++) { dump(t.first[i]); cerr << (i == t.second - 1 ? "" : ", "); } cerr << " ]"; } void trace() { cerr << endl; } template void trace(Head&& head, Tail&&... tail) { cerr << " "; dump(head); if (sizeof...(tail) != 0) cerr << ","; trace(forward(tail)...); } } // namespace DebugImpl #ifdef NyaanDebug #define trc(...) \ do { \ cerr << "## " << #__VA_ARGS__ << " = "; \ DebugImpl::trace(__VA_ARGS__); \ } while (0) #else #define trc(...) #endif // macro #define each(x, v) for (auto&& x : v) #define each2(x, y, v) for (auto&& [x, y] : v) #define all(v) (v).begin(), (v).end() #define rep(i, N) for (long long i = 0; i < (long long)(N); i++) #define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--) #define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++) #define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--) #define reg(i, a, b) for (long long i = (a); i < (b); i++) #define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--) #define repc(i, a, cond) for (long long i = (a); (cond); i++) #define enm(i, val, vec) \ for (long long i = 0; i < (long long)(vec).size(); i++) \ if (auto& val = vec[i]; false) \ ; \ else #define ini(...) \ int __VA_ARGS__; \ in(__VA_ARGS__) #define inl(...) \ long long __VA_ARGS__; \ in(__VA_ARGS__) #define ins(...) \ string __VA_ARGS__; \ in(__VA_ARGS__) #define inc(...) \ char __VA_ARGS__; \ in(__VA_ARGS__) #define in2(s, t) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i]); \ } #define in3(s, t, u) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i]); \ } #define in4(s, t, u, v) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i], v[i]); \ } #define die(...) \ do { \ Nyaan::out(__VA_ARGS__); \ return; \ } while (0) namespace Nyaan { void solve(); } int main() { Nyaan::solve(); } using namespace Nyaan; namespace inner { using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; template T gcd(T a, T b) { while (b) swap(a %= b, b); return a; } template T inv(T a, T p) { T b = p, x = 1, y = 0; while (a) { T q = b / a; swap(a, b %= a); swap(x, y -= q * x); } assert(b == 1); return y < 0 ? y + p : y; } template T modpow(T a, U n, T p) { T ret = 1 % p; for (; n; n >>= 1, a = U(a) * a % p) if (n & 1) ret = U(ret) * a % p; return ret; } } // namespace inner namespace my_rand { // [0, 2^64 - 1) uint64_t rng() { static uint64_t x_ = uint64_t(chrono::duration_cast( chrono::high_resolution_clock::now().time_since_epoch()) .count()) * 10150724397891781847ULL; x_ ^= x_ << 7; return x_ ^= x_ >> 9; } // [l, r) int64_t randint(int64_t l, int64_t r) { assert(l < r); return l + rng() % (r - l); } // choose n numbers from [l, r) without overlapping vector randset(int64_t l, int64_t r, int64_t n) { assert(l <= r && n <= r - l); unordered_set s; for (int64_t i = n; i; --i) { int64_t m = randint(l, r + 1 - i); if (s.find(m) != s.end()) m = r - i; s.insert(m); } vector ret; for (auto& x : s) ret.push_back(x); return ret; } // [0.0, 1.0) double rnd() { union raw_cast { double t; uint64_t u; }; constexpr uint64_t p = uint64_t(1023 - 64) << 52; return rng() * ((raw_cast*)(&p))->t; } template void randshf(vector& v) { int n = v.size(); for (int loop = 0; loop < 2; loop++) for (int i = 0; i < n; i++) swap(v[i], v[randint(0, n)]); } } // namespace my_rand using my_rand::randint; using my_rand::randset; using my_rand::randshf; using my_rand::rnd; using my_rand::rng; struct ArbitraryLazyMontgomeryModInt { using mint = ArbitraryLazyMontgomeryModInt; using i32 = int32_t; using u32 = uint32_t; using u64 = uint64_t; static u32 mod; static u32 r; static u32 n2; static u32 get_r() { u32 ret = mod; for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret; return ret; } static void set_mod(u32 m) { assert(m < (1 << 30)); assert((m & 1) == 1); mod = m; n2 = -u64(m) % m; r = get_r(); assert(r * mod == 1); } u32 a; ArbitraryLazyMontgomeryModInt() : a(0) {} ArbitraryLazyMontgomeryModInt(const int64_t &b) : a(reduce(u64(b % mod + mod) * n2)){}; static u32 reduce(const u64 &b) { return (b + u64(u32(b) * u32(-r)) * mod) >> 32; } mint &operator+=(const mint &b) { if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod; return *this; } mint &operator-=(const mint &b) { if (i32(a -= b.a) < 0) a += 2 * mod; return *this; } mint &operator*=(const mint &b) { a = reduce(u64(a) * b.a); return *this; } mint &operator/=(const mint &b) { *this *= b.inverse(); return *this; } mint operator+(const mint &b) const { return mint(*this) += b; } mint operator-(const mint &b) const { return mint(*this) -= b; } mint operator*(const mint &b) const { return mint(*this) *= b; } mint operator/(const mint &b) const { return mint(*this) /= b; } bool operator==(const mint &b) const { return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a); } bool operator!=(const mint &b) const { return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a); } mint operator-() const { return mint() - mint(*this); } mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const mint &b) { return os << b.get(); } friend istream &operator>>(istream &is, mint &b) { int64_t t; is >> t; b = ArbitraryLazyMontgomeryModInt(t); return (is); } mint inverse() const { return pow(mod - 2); } u32 get() const { u32 ret = reduce(a); return ret >= mod ? ret - mod : ret; } static u32 get_mod() { return mod; } }; typename ArbitraryLazyMontgomeryModInt::u32 ArbitraryLazyMontgomeryModInt::mod; typename ArbitraryLazyMontgomeryModInt::u32 ArbitraryLazyMontgomeryModInt::r; typename ArbitraryLazyMontgomeryModInt::u32 ArbitraryLazyMontgomeryModInt::n2; struct montgomery64 { using mint = montgomery64; using i64 = int64_t; using u64 = uint64_t; using u128 = __uint128_t; static u64 mod; static u64 r; static u64 n2; static u64 get_r() { u64 ret = mod; for (i64 i = 0; i < 5; ++i) ret *= 2 - mod * ret; return ret; } static void set_mod(u64 m) { assert(m < (1LL << 62)); assert((m & 1) == 1); mod = m; n2 = -u128(m) % m; r = get_r(); assert(r * mod == 1); } u64 a; montgomery64() : a(0) {} montgomery64(const int64_t &b) : a(reduce((u128(b) + mod) * n2)){}; static u64 reduce(const u128 &b) { return (b + u128(u64(b) * u64(-r)) * mod) >> 64; } mint &operator+=(const mint &b) { if (i64(a += b.a - 2 * mod) < 0) a += 2 * mod; return *this; } mint &operator-=(const mint &b) { if (i64(a -= b.a) < 0) a += 2 * mod; return *this; } mint &operator*=(const mint &b) { a = reduce(u128(a) * b.a); return *this; } mint &operator/=(const mint &b) { *this *= b.inverse(); return *this; } mint operator+(const mint &b) const { return mint(*this) += b; } mint operator-(const mint &b) const { return mint(*this) -= b; } mint operator*(const mint &b) const { return mint(*this) *= b; } mint operator/(const mint &b) const { return mint(*this) /= b; } bool operator==(const mint &b) const { return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a); } bool operator!=(const mint &b) const { return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a); } mint operator-() const { return mint() - mint(*this); } mint pow(u128 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const mint &b) { return os << b.get(); } friend istream &operator>>(istream &is, mint &b) { int64_t t; is >> t; b = montgomery64(t); return (is); } mint inverse() const { return pow(mod - 2); } u64 get() const { u64 ret = reduce(a); return ret >= mod ? ret - mod : ret; } static u64 get_mod() { return mod; } }; typename montgomery64::u64 montgomery64::mod, montgomery64::r, montgomery64::n2; namespace fast_factorize { using u64 = uint64_t; template bool miller_rabin(u64 n, vector as) { if (mint::get_mod() != n) mint::set_mod(n); u64 d = n - 1; while (~d & 1) d >>= 1; mint e{1}, rev{int64_t(n - 1)}; for (u64 a : as) { if (n <= a) break; u64 t = d; mint y = mint(a).pow(t); while (t != n - 1 && y != e && y != rev) { y *= y; t *= 2; } if (y != rev && t % 2 == 0) return false; } return true; } bool is_prime(u64 n) { if (~n & 1) return n == 2; if (n <= 1) return false; if (n < (1LL << 30)) return miller_rabin(n, {2, 7, 61}); else return miller_rabin( n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022}); } template T pollard_rho(T n) { if (~n & 1) return 2; if (is_prime(n)) return n; if (mint::get_mod() != n) mint::set_mod(n); mint R, one = 1; auto f = [&](mint x) { return x * x + R; }; auto rnd_ = [&]() { return rng() % (n - 2) + 2; }; while (1) { mint x, y, ys, q = one; R = rnd_(), y = rnd_(); T g = 1; constexpr int m = 128; for (int r = 1; g == 1; r <<= 1) { x = y; for (int i = 0; i < r; ++i) y = f(y); for (int k = 0; g == 1 && k < r; k += m) { ys = y; for (int i = 0; i < m && i < r - k; ++i) q *= x - (y = f(y)); g = inner::gcd(q.get(), n); } } if (g == n) do g = inner::gcd((x - (ys = f(ys))).get(), n); while (g == 1); if (g != n) return g; } exit(1); } vector inner_factorize(u64 n) { if (n <= 1) return {}; u64 p; if (n <= (1LL << 30)) p = pollard_rho(n); else p = pollard_rho(n); if (p == n) return {p}; auto l = inner_factorize(p); auto r = inner_factorize(n / p); copy(begin(r), end(r), back_inserter(l)); return l; } vector factorize(u64 n) { auto ret = inner_factorize(n); sort(begin(ret), end(ret)); return ret; } using i64 = int64_t; map factor_count(u64 n) { map mp; for (auto &x : factorize(n)) mp[x]++; return mp; } vector divisors(u64 n) { if (n == 0) return {}; vector> v; for (auto &p : factor_count(n)) v.push_back(p); vector ret; auto f = [&](auto rec, int i, u64 x) -> void { if (i == (int)v.size()) { ret.push_back(x); return; } for (int j = v[i].second;; --j) { rec(rec, i + 1, x); if (j == 0) break; x *= v[i].first; } }; f(f, 0, 1); sort(begin(ret), end(ret)); return ret; } } // namespace fast_factorize using fast_factorize::divisors; using fast_factorize::factor_count; using fast_factorize::factorize; using fast_factorize::is_prime; /** * @brief 高速素因数分解(Miller Rabin/Pollard's Rho) * @docs docs/prime/fast-factorize.md */ void Nyaan::solve() { /**/ // // f(x, n) : xまで処理したときのnに対する答え、とおく // f(x, n) = f(x-1, n) + f(x-1, n/(x-1)) - f(x-1, n/x) (x is prime) // 更新範囲を考えると? // n/(x-1)とn/xが相異なる… n >= xが必要? // x > \sq(n)のとき... inl(N); vector ns{0}; vector kouho; for (ll i = N; i > 0; i = N / (N / i + 1)) { ns.push_back(i); kouho.push_back(i + 1); } { vl buf; each(x, kouho) if (is_prime(x)) buf.push_back(x); sort(all(buf)); swap(buf, kouho); } exit(1); vector h(ns); int sq = sqrt(N); auto idx = [&](ll x) { return x ? x <= sq ? sz(h) - x : N / x : 0; }; each(p, kouho) { for (int i = 1; i < sz(h); i++) { if (ns[i] / p != ns[i] / (p - 1)){ h[i] += h[idx(ns[i] / (p - 1))] - h[idx(ns[i] / p)]; } } trc(p, h); } out(h[1]); //*/ /** #include "multiplicative-function/mf-famous-series.hpp" auto tot = totient(10000); // trc(tot); int n = 50; vi cnt(n + 1); rep(i, 10001) if (i and tot[i] <= n) cnt[tot[i]]++; trc(cnt); auto dirichlet = [](vi a, vi b) { int n_ = sz(a) - 1; vi c(n_ + 1); rep1(i, n_) { rep1(j, n_) { if (i * j > n_) break; c[i * j] += a[i] * b[j]; } } return c; }; vi a(n + 1, 1); a[0] = 0; for (auto p : vi{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}) { vi b(n + 1); b[1]++, b[p - 1]++, b[p]--; a = dirichlet(a, b); trc(p, a); trc(accumulate(all(a),0)); } trc(a); //*/ }