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; }