test/hackerrank/cube-loving-numbers.multiple_mobius.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 12:11:12+09:00
• Problem: https://www.hackerrank.com/contests/university-codesprint-5/challenges/cube-loving-numbers

Depends on

• CSR 表現を用いた二次元配列 他 (src/Internal/ListRange.hpp)
• 素数の列挙 (src/NumberTheory/enumerate_primes.hpp)
• 乗法的関数テーブルや gcd 畳み込みなど (src/NumberTheory/tables.hpp)

Code

// competitive-verifier: PROBLEM https://www.hackerrank.com/contests/university-codesprint-5/challenges/cube-loving-numbers
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include "src/NumberTheory/tables.hpp"
// 倍数メビウス
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int T;
 cin >> T;
 long long f[1'000'010];
 while (T--) {
  long long N, a= 2, ans= 0;
  cin >> N;
  for (; a * a * a <= N; a++) f[a]= N / (a * a * a);
  vector<long long> g(f, f + a);
  multiple_mobius(g);
  for (; --a >= 2;) ans+= g[a];
  cout << ans << '\n';
 }
 return 0;
}

#line 1 "test/hackerrank/cube-loving-numbers.multiple_mobius.test.cpp"
// competitive-verifier: PROBLEM https://www.hackerrank.com/contests/university-codesprint-5/challenges/cube-loving-numbers
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#line 2 "src/NumberTheory/enumerate_primes.hpp"
#include <algorithm>
#include <cstdint>
#line 4 "src/Internal/ListRange.hpp"
#include <iterator>
#include <type_traits>
#define _LR(name, IT, CT) \
 template <class T> struct name { \
  using Iterator= typename std::vector<T>::IT; \
  Iterator bg, ed; \
  Iterator begin() const { return bg; } \
  Iterator end() const { return ed; } \
  size_t size() const { return std::distance(bg, ed); } \
  CT &operator[](int i) const { return bg[i]; } \
 }
_LR(ListRange, iterator, T);
_LR(ConstListRange, const_iterator, const T);
#undef _LR
template <class T> struct CSRArray {
 std::vector<T> dat;
 std::vector<int> p;
 size_t size() const { return p.size() - 1; }
 ListRange<T> operator[](int i) { return {dat.begin() + p[i], dat.begin() + p[i + 1]}; }
 ConstListRange<T> operator[](int i) const { return {dat.cbegin() + p[i], dat.cbegin() + p[i + 1]}; }
};
template <template <class> class F, class T> std::enable_if_t<std::disjunction_v<std::is_same<F<T>, ListRange<T>>, std::is_same<F<T>, ConstListRange<T>>, std::is_same<F<T>, CSRArray<T>>>, std::ostream &> operator<<(std::ostream &os, const F<T> &r) {
 os << '[';
 for (int _= 0, __= r.size(); _ < __; ++_) os << (_ ? ", " : "") << r[_];
 return os << ']';
}
#line 5 "src/NumberTheory/enumerate_primes.hpp"
namespace nt_internal {
using namespace std;
vector<int> ps, lf;
void sieve(int N) {
 static int n= 2;
 if (n > N) return;
 if (lf.resize((N + 1) >> 1); n == 2) ps.push_back(n++);
 int M= (N - 1) / 2;
 for (int j= 1, e= ps.size(); j < e; ++j) {
  int p= ps[j];
  if (int64_t(p) * p > N) break;
  for (auto k= int64_t(p) * max(n / p / 2 * 2 + 1, p) / 2; k <= M; k+= p) lf[k]+= p * !lf[k];
 }
 for (; n <= N; n+= 2)
  if (!lf[n >> 1]) {
   ps.push_back(lf[n >> 1]= n);
   for (auto j= int64_t(n) * n / 2; j <= M; j+= n) lf[j]+= n * !lf[j];
  }
}
ConstListRange<int> enumerate_primes() { return {ps.cbegin(), ps.cend()}; }
ConstListRange<int> enumerate_primes(int N) {
 sieve(N);
 return {ps.cbegin(), upper_bound(ps.cbegin(), ps.cend(), N)};
}
int least_prime_factor(int n) { return n & 1 ? sieve(n), lf[(n >> 1)] : 2; }
// f(p,e) := f(p^e)
template <class T, class F> vector<T> completely_multiplicative_table(int N, const F &f) {
 vector<T> ret(N + 1);
 sieve(N);
 for (int n= 3, i= 1; n <= N; n+= 2, ++i) ret[n]= lf[i] == n ? f(n, 1) : ret[lf[i]] * ret[n / lf[i]];
 if (int n= 4; 2 <= N)
  for (T t= ret[2]= f(2, 1); n <= N; n+= 2) ret[n]= t * ret[n >> 1];
 return ret[1]= 1, ret;
}
}
using nt_internal::enumerate_primes, nt_internal::least_prime_factor, nt_internal::completely_multiplicative_table;
// O(N log k / log N + N)
template <class T> static std::vector<T> pow_table(int N, uint64_t k) {
 if (k == 0) return std::vector<T>(N + 1, 1);
 auto f= [k](int p, int) {
  T ret= 1, b= p;
  for (auto e= k;; b*= b) {
   if (e & 1) ret*= b;
   if (!(e>>= 1)) return ret;
  }
 };
 return completely_multiplicative_table<T>(N, f);
}
#line 3 "src/NumberTheory/tables.hpp"
namespace nt_internal {
vector<int> lfw;
vector<char> lfe;
void set_lfe(int N) {
 static int n= 3, i= 1;
 if (n > N) return;
 for (sieve(N), lfw.resize((N + 1) >> 1), copy(lf.begin() + i, lf.begin() + ((N + 1) >> 1), lfw.begin() + i), lfe.resize(((N + 1) >> 1), 1); n <= N; n+= 2, ++i)
  if (int j= (n / lf[i]) >> 1; lf[i] == lf[j]) lfe[i]+= lfe[j], lfw[i]*= lfw[j];
}
// O(log n)
vector<pair<int, short>> factorize(int n) {
 vector<pair<int, short>> ret;
 if (short t; !(n & 1)) ret.emplace_back(2, t= __builtin_ctz(n)), n>>= t;
 if (int i= n >> 1; n > 1)
  for (set_lfe(n); n > 1; i= n >> 1) ret.emplace_back(lf[i], lfe[i]), n/= lfw[i];
 return ret;
}
// f(p,e) := f(p^e)
template <class T, class F> vector<T> multiplicative_table(int N, const F &f) {
 vector<T> ret(N + 1);
 set_lfe(N);
 for (int n= 3, i= 1; n <= N; n+= 2, ++i) ret[n]= lfw[i] == n ? f(lf[i], lfe[i]) : ret[lfw[i]] * ret[n / lfw[i]];
 for (int n= 2, t; n <= N; n+= 2) t= __builtin_ctz(n), ret[n]= n & (n - 1) ? ret[n & -n] * ret[n >> t] : f(2, t);
 return ret[1]= 1, ret;
}
// O(N)
template <class T= int> vector<T> mobius_table(int N) {
 vector<T> ret(N + 1);
 set_lfe(N), ret[1]= 1;
 for (int n= 3, i= 1; n <= N; n+= 2, ++i) ret[n]= lfw[i] == n ? -(lfe[i] == 1) : ret[lfw[i]] * ret[n / lfw[i]];
 for (int n= 2; n <= N; n+= 4) ret[n]= -ret[n >> 1];
 return ret;
}
// O(N)
template <class T= int> vector<T> totient_table(int N) {
 vector<T> ret(N + 1);
 set_lfe(N), ret[1]= 1;
 for (int n= 3, i= 1; n <= N; n+= 2, ++i) ret[n]= lfw[i] == n ? lf[i] == n ? n - 1 : ret[n / lf[i]] * lf[i] : ret[lfw[i]] * ret[n / lfw[i]];
 for (int n= 2; n <= N; n+= 4) ret[n]= ret[n >> 1];
 for (int n= 4; n <= N; n+= 4) ret[n]= ret[n >> 1] << 1;
 return ret;
}
}
using nt_internal::factorize, nt_internal::multiplicative_table, nt_internal::mobius_table, nt_internal::totient_table;
// f -> g s.t. g(n) = sum_{m|n} f(m), O(N log log N)
template <typename T> void divisor_zeta(std::vector<T> &a) {
 for (auto p: enumerate_primes(a.size() - 1))
  for (int j= 1, e= a.size(); p * j < e; ++j) a[p * j]+= a[j];
}
// a -> h s.t. a(n) = sum_{m|n} h(m), O(N log log N)
template <typename T> void divisor_mobius(std::vector<T> &a) {
 for (auto p: enumerate_primes(a.size() - 1))
  for (int j= (a.size() - 1) / p; j; --j) a[p * j]-= a[j];
}
// O(N log log N)
template <typename T> std::vector<T> lcm_convolve(std::vector<T> a, std::vector<T> b) {
 std::size_t N= std::max(a.size(), b.size());
 for (a.resize(N), b.resize(N), divisor_zeta(a), divisor_zeta(b); N--;) a[N]*= b[N];
 return divisor_mobius(a), a;
}
// a -> g s.t. g(n) = sum_{n|m} a(m), O(N log log N)
template <typename T> static void multiple_zeta(std::vector<T> &a) {
 for (auto p: enumerate_primes(a.size() - 1))
  for (int j= (a.size() - 1) / p; j; --j) a[j]+= a[p * j];
}
// a -> h s.t. a(n) = sum_{n|m} h(m), O(N log log N)
template <typename T> static void multiple_mobius(std::vector<T> &a) {
 for (auto p: enumerate_primes(a.size() - 1))
  for (int j= 1, e= a.size(); p * j < e; ++j) a[j]-= a[p * j];
}
// O(N log log N)
template <typename T> static std::vector<T> gcd_convolve(std::vector<T> a, std::vector<T> b) {
 std::size_t N= std::max(a.size(), b.size());
 for (a.resize(N), b.resize(N), multiple_zeta(a), multiple_zeta(b); N--;) a[N]*= b[N];
 return multiple_mobius(a), a;
}
#line 7 "test/hackerrank/cube-loving-numbers.multiple_mobius.test.cpp"
// 倍数メビウス
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int T;
 cin >> T;
 long long f[1'000'010];
 while (T--) {
  long long N, a= 2, ans= 0;
  cin >> N;
  for (; a * a * a <= N; a++) f[a]= N / (a * a * a);
  vector<long long> g(f, f + a);
  multiple_mobius(g);
  for (; --a >= 2;) ans+= g[a];
  cout << ans << '\n';
 }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00	AC	10 ms	11 MB
g++-13	01	AC	10 ms	12 MB
g++-13	02	AC	9 ms	12 MB
g++-13	03	AC	9 ms	11 MB
g++-13	04	AC	9 ms	11 MB
g++-13	05	AC	10 ms	11 MB
g++-13	06	AC	162 ms	21 MB
g++-13	07	AC	136 ms	20 MB
g++-13	08	AC	135 ms	20 MB
g++-13	09	AC	121 ms	21 MB
g++-13	10	AC	146 ms	21 MB
g++-13	11	AC	109 ms	29 MB
g++-13	12	AC	106 ms	24 MB
g++-13	13	AC	88 ms	18 MB
g++-13	14	AC	111 ms	22 MB
g++-13	15	AC	119 ms	27 MB
g++-13	16	AC	149 ms	21 MB
g++-13	17	AC	149 ms	21 MB
g++-13	18	AC	148 ms	21 MB
g++-13	19	AC	149 ms	22 MB
g++-13	20	AC	161 ms	21 MB
clang++-18	00	AC	5 ms	4 MB
clang++-18	01	AC	4 ms	4 MB
clang++-18	02	AC	4 ms	4 MB
clang++-18	03	AC	4 ms	4 MB
clang++-18	04	AC	4 ms	4 MB
clang++-18	05	AC	4 ms	4 MB
clang++-18	06	AC	156 ms	21 MB
clang++-18	07	AC	130 ms	19 MB
clang++-18	08	AC	130 ms	19 MB
clang++-18	09	AC	126 ms	22 MB
clang++-18	10	AC	140 ms	21 MB
clang++-18	11	AC	113 ms	29 MB
clang++-18	12	AC	101 ms	24 MB
clang++-18	13	AC	80 ms	16 MB
clang++-18	14	AC	108 ms	20 MB
clang++-18	15	AC	123 ms	25 MB
clang++-18	16	AC	148 ms	21 MB
clang++-18	17	AC	155 ms	21 MB
clang++-18	18	AC	156 ms	21 MB
clang++-18	19	AC	156 ms	21 MB
clang++-18	20	AC	148 ms	21 MB

Back to top page