けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2706 幾何問題を解こう

問題へのリンク

問題概要

整数  p, q があたえられる。
 b 進法で有理数 p/q を小数で表したときに有限小数となるような最小の 2 以上の整数  b を求めよ。

制約

  •  0 <  p <  q \le 10^{9}

考えたこと

とりあえず p/q を約分しておく。
そして、q を素因数分解したときの、指数部を全部 1 にしたものが答えになる。

#include <iostream>
using namespace std;

long long GCD(long long a, long long b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}

int main() {
    long long p, q; cin >> p >> q;
    long long d = GCD(p, q);
    q /= d;
    for (long long v = 2; v*v <= q; ++v) {
        while (q % (v*v)== 0) q /= v;
    }
    cout << q << endl;
}