JAG 夏合宿 2015 Day2 A: 幾何問題を解こう

解法

N^k 進数で表せる小数は N 進数で表せる。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

set<int> yakusu(int B) {
  set<int> p;
  int s = sqrt(B) + 10;
  for (int i = 1; i <= s; i++) {
    if (B % i == 0) {
      p.insert(i);
      p.insert(B / i);
    }
  }
  return p;
}

set<int> soinsu(int B) {
  set<int> p;
  int s = sqrt(B) + 10;
  if (B % 2 == 0) p.insert(2);
  while (B % 2 == 0) B /= 2;
  for (int i = 3; i <= s; i += 2) {
    if (B % i == 0) p.insert(i);
    while (B % i == 0) B /= i;
  }
  if (B > 1) p.insert(B);
  return p;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll A, B;
  cin >> A >> B;

  set<int> a = yakusu(A);
  ll ans = B;
  for (int y : a) {
    if (B % y == 0) {
      set<int> s = soinsu(B / y);
      ll pro = 1;
      for (int ss : s) pro *= ss;
      ans = min(ans, pro);
    }
  }

  cout << ans << endl;
}