Codeforces/1933/c.cpp

#pragma region includes
#include <algorithm>
#include <array>
#include <bit>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#pragma endregion includes

#pragma region helpers

#pragma region aliases
#define LOOP(var, n) for (auto var = 0; var < n; ++var)

template <typename T>
using V = std::vector<T>;

template <typename K, typename V>
using M = std::map<K, V>;

template <typename T>
using S = std::set<T>;

template <typename T>
using Q = std::deque<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;
#pragma endregion /* aliases */

#pragma region data structures
template <typename T>
struct max_heap {
  using container = std::vector<T>;

  typename container::size_type size() const { return h.size(); }

  void push(T item) {
    h.push_back(item);
    std::push_heap(h.begin(), h.end());
  }

  T pop() {
    std::pop_heap(h.begin(), h.end());
    T item = std::move(h.back());
    h.pop_back();
    return item;
  }

 private:
  container h;
};

template <typename T>
struct min_heap {
  using container = std::vector<T>;

  typename container::size_type size() const { return h.size(); }

  void push(T item) {
    h.push_back(item);
    std::push_heap(h.begin(), h.end(), std::greater<>{});
  }

  T pop() {
    std::pop_heap(h.begin(), h.end(), std::greater<>{});
    T item = std::move(h.back());
    h.pop_back();
    return item;
  }

 private:
  container h;
};
#pragma endregion /* data structures */

#pragma region debug
void dbg_out() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
  std::cerr << ' ' << H;
  dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...)                                                           \
  std::cerr << '[' << __FILE__ << ':' << __LINE__ << "] (" << #__VA_ARGS__ \
            << "):",                                                       \
      dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
#pragma endregion debug

#pragma region functional
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template <class Fun>
class y_combinator_result {
  Fun fun_;

 public:
  template <class T>
  explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}
  template <class... Args>
  decltype(auto) operator()(Args &&...args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};
template <class Fun>
decltype(auto) y_combinator(Fun &&fun) {
  return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
#pragma endregion /* functional */

#pragma region input
template <typename Container>
void collect(Container &c, std::size_t size) {
  auto it = std::inserter(c, c.begin());

  for (auto i = 0u; i < size; ++i) {
    typename Container::value_type x;
    std::cin >> x;
    it = std::move(x);
  }
}

template <typename Container>
Container collect(std::size_t size) {
  Container c{};
  collect(c, size);
  return c;
}

template <typename T>
std::map<T, std::size_t> collect_count(std::size_t size) {
  std::map<T, std::size_t> counts;

  for (auto i = 0u; i < size; ++i) {
    T x;
    std::cin >> x;
    ++counts[x];
  }

  return counts;
}
#pragma endregion /* input */

#pragma region math
long pow(long base, long exp) {
  if (exp == 0) return 1;
  long half = pow(base, exp / 2);
  if (exp % 2 == 0) return half * half;
  return half * half * base;
}

template <typename T>
T isqrt(T x) {
  assert(x >= 0);

  auto max_shift = 8 * sizeof(T) - 1;
  auto shift = (max_shift - std::countl_zero(x)) & ~1;
  auto bit = 1 << shift;

  T result = 0;
  while (bit != 0) {
    if (x >= (result + bit)) {
      x -= result + bit;
      result = (result >> 1) + bit;
    } else {
      result = (result >> 1);
    }
    bit = bit >> 2;
  }

  return result;
}

template <std::int64_t MODULO = 1000000007>
struct Z {
  Z(std::int64_t x = 0) : x(x % MODULO) {}

  Z pow(std::uint32_t exp) const {
    auto ans = 1;
    auto base = x;

    for (; exp > 0; exp >>= 1) {
      if (exp % 2 == 1) {
        ans *= base;
      }

      base *= base;
    }

    return ans;
  }

  Z inv() const {
    assert(x != 0);
    return pow(MODULO - 2);
  }

  Z operator-() const { return {-x}; }
  Z operator+=(const Z &rhs) { x = (x + rhs.x) % MODULO; }
  Z operator-=(const Z &rhs) { x = (x - rhs.x) % MODULO; }
  Z operator*=(const Z &rhs) { x = (x * rhs.x) % MODULO; }
  Z operator/=(const Z &rhs) { x = (x * rhs.inv().x) % MODULO; }

  friend Z operator+(Z lhs, const Z &rhs) { return lhs += rhs; }
  friend Z operator-(Z lhs, const Z &rhs) { return lhs -= rhs; }
  friend Z operator*(Z lhs, const Z &rhs) { return lhs *= rhs; }
  friend Z operator/(Z lhs, const Z &rhs) { return lhs /= rhs; }

  friend std::istream &operator>>(std::istream &is, Z &z) {
    is >> z.x;
    z.x %= MODULO;
    return is;
  }

  friend std::ostream &operator<<(std::ostream &os, const Z &z) {
    return os << z.x;
  }

 private:
  std::int64_t x;
};
#pragma endregion /* math */

#pragma region output
template <typename T, typename U>
std::ostream &operator<<(std::ostream &os, std::pair<T, U> const &p) {
  return os << p.first << " " << p.second;
}

template <typename C, typename T = typename std::enable_if<
                          !std::is_same<C, std::string>::value,
                          typename C::value_type>::type>
std::ostream &operator<<(std::ostream &os, const C &v) {
  std::string sep;
  for (const T &x : v) {
    os << sep << x, sep = " ";
  }

  return os;
}

template <typename T>
inline void answer(const T &ans) {
#ifdef LOCAL
  std::cout << "Answer: ";
#endif

  std::cout << ans << "\n";
}

inline void yes() { answer("YES"); }
inline void no() { answer("NO"); }
inline void yesno(bool ans) { answer(ans ? "YES" : "NO"); }
#pragma endregion /* output */

#pragma region rng
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
#pragma endregion /* rng */

#pragma endregion /* helpers */

// for ‹N› test cases, uncomment for single test case
// #define SINGLE

namespace solution {

using namespace std;

auto count_ks(S<int>& ks, int l, int a, int b) -> int {
  ks.insert(l);

  if (l % a == 0) {
    count_ks(ks, l / a, a, b);
  }
  if (l % b == 0) {
    count_ks(ks, l / b, a, b);
  }

  return static_cast<int>(ks.size());
}

void solve() {
  int a, b, l;
  cin >> a >> b >> l;

  S<int> ks;
  answer(count_ks(ks, l, a, b));
}

void tests() {
  // TODO
}

}  // namespace solution

using namespace solution;

#ifdef TEST

int main(void) {
  tests();
  return 0;
}

#else

int main(void) {
  int N = 1;

#ifndef SINGLE

  std::cin >> N;

#endif

  while (N-- > 0) {
    solve();
  }

  return 0;
}

#endif