(200726) 코드포스

Codeforces materials usage license (v. 0.1) 에 따라 codeforces.com 의 문제임을 알립니다.

Original problem link: Problem - 1360D - Codeforces


Example

Input

5
8 7
8 1
6 10
999999733 999999732
999999733 999999733

Output

2
8
1
999999733
1


Common codes for Codeforces
#include <algorithm>
#include <array>
#include <cmath>
#include <functional> 
#include <iostream>
#include <memory>
#include <queue>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <vector>

namespace predefined {

#ifdef CODEFORCES_DEBUG
  constexpr bool kIsDebug = true;
#else
  constexpr bool kIsDebug = false;
#endif

enum class LogType {
  INFO,
  DEBUG
};

template <LogType Type, bool... Bools>
struct Log;

template <>
struct Log<LogType::INFO> {
  Log() {}
  ~Log() { std::cout << '\n'; }

  template <typename T>
  Log& operator<< (const T &t) {
    std::cout << t;
    return *this;
  }
};

template <>
struct Log<LogType::DEBUG, true>{
  Log() {}
  ~Log() { std::cout << '\n'; }

  void Open() {
    freopen("input.txt", "r", stdin);
  }

  template <typename T>
  Log& operator<< (const T &t) {
    std::cout << t;
    return *this;
  }
};

template <>
struct Log<LogType::DEBUG, false> {
  Log() {}
  ~Log() {}

  void Open() {}

  template <typename T>
  Log& operator<< (const T &t) { return *this; }
};

namespace solver {

using SolveFunc = std::function<void()>;

template<typename MultiRunner>
void Run(SolveFunc solve_func);

template<>
void Run<std::true_type>(SolveFunc solve_func) {
  int test_case;
  std::cin >> test_case;

  while (test_case--) {
    solve_func();
  }
}

template<>
void Run<std::false_type>(SolveFunc solve_func) {
  solve_func();
}

} // solver

template <bool MultiTest>
struct Solver {
  constexpr static bool condition = MultiTest | kIsDebug;
  typedef typename std::conditional<condition, std::true_type, std::false_type>::type run_type;

  explicit Solver(solver::SolveFunc solve_func) {
    solver::Run<run_type>(solve_func);
  }
};

template<typename T>
struct BoolMap {
  explicit BoolMap(const T &_true_value, const T &_false_value) 
    : true_value(_true_value),
      false_value(_false_value) {}

  const T true_value;
  const T false_value;

  const T inline GetValue(const bool bool_key) const {
    return bool_key ? true_value : false_value;  
  };
};

}  // predefined;

#define LOG_INFO predefined::Log<predefined::LogType::INFO>()
#define LOG_DEBUG predefined::Log<predefined::LogType::DEBUG, predefined::kIsDebug>()
#define LOG(LEVEL) LOG_##LEVEL
#define LABEL(variable_name) #variable_name << ": " << variable_name << " "

#define INIT_ANSWER(type, true_value, false_value) \
  const predefined::BoolMap<type> predefined_bool_map(true_value, false_value)
#define INIT_STRING_ANSWER(true_string, false_string) \
  INIT_ANSWER(std::string, true_string, false_string)
#define GET_ANSWER(bool_key) \
  predefined_bool_map.GetValue(bool_key)

#define INIT_CODEFORCES() \
  std::ios::sync_with_stdio(false); \
  std::cin.tie(NULL); \
  LOG(DEBUG).Open();

1 Like

매일 이렇게 꾸준히 푸시는거 존경합니다
열심히 하세요!

2 Likes

주말에 머리가 돌아가지 않네요 ㅎㅎ 겨우 풀었습니다.

1360D

40000잡고 그냥 linear하게 돌려버리네요.
소수를 구해서 최적화 할 필요 없으니까, prime구하는 init함수랑 dfs가 필요가 없어지네요.
코드 속도는 15ms 빠르지만 작성 속도는 10배 차이 나는 것 같군요.

namespace {
using namespace std;
 
constexpr bool kMultiTestCase = true;
using Solver = predefined::Solver<kMultiTestCase>;
 
constexpr int kMaxN = 1e9;
}  // unnamed namespace;
 
int Gcd(int a,int b){
	while (a && b) a > b ? a %= b : b %= a;
	return a | b;
}
 
vector<int> primes;
 
void Init() {
  const int sq = sqrt(kMaxN);
  vector<bool> visited(sq + 1, false);
  for (int i = 2; i * i < kMaxN; ++i) {
    if (visited[i] == false) {
      primes.push_back(i);
      for(int j = i; j < sq; j += i) {
        visited[j] = true;
      }
    }
  }
}
 
vector<pair<int, int>> prime_count;
int a, b;
int ans;
int now;
 
void Dfs(int index) {
  if (now <= b && ans < now) {
    ans = now;
  }
  if(index == prime_count.size()) return;
 
  int div = 1;
  Dfs(index + 1);
  for (int i = 0; i < prime_count[index].second; ++i) {
    now *= prime_count[index].first;
    div *= prime_count[index].first;
    Dfs(index + 1);
  }
  now /= div;
  return;
}
 
void Solve() {
  cin >> a >> b;
 
  if (b >= a) {
    LOG_INFO << 1;
    return;
  }
 
  ans = 1;
  now = 1;
  prime_count.clear();
 
  int a_temp = a;
  for (const auto prime : primes) {
    if (a_temp == 1) break;
 
    if (a_temp % prime == 0) {
      prime_count.push_back(make_pair(prime, 1));
      a_temp /= prime;
      while (a_temp % prime == 0) {
        ++prime_count.back().second;
        a_temp /= prime;
      }
    }
  }
  if (a_temp != 1) {
    prime_count.push_back(make_pair(a_temp, 1));
  }
 
  Dfs(0);
  LOG_INFO << a / ans;
}
 
int main(int argc, char** argv) {
  INIT_CODEFORCES();
 
  Init();
  Solver([](){Solve();});
 
  return 0;
}

https://codeforces.com/contest/1360/submission/81206851
레드코더는 20줄 안에 간단하게 풀어버리는군요 ㅎㅎ…

목표를 가지고 꾸준히 하는 것이 뭐든간에 중요하다고 생각합니다.

이번 주말에 약간 방전되는 느낌이었는데 응원 덕에 힘이납니다.파이팅!

주말엔 쉬어요. 쉴땐 쉬는게 정말 중요합니다.

1 Like

타이포 멋지네요.

1 Like