AOJ 2706 幾何問題を解こう (JAG 夏合宿 2015 day2-A) (200 点)

問題へのリンク

問題概要

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

制約

• < <

考えたこと

とりあえず 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;
}