AOJ2706 幾何問題を解こう
(Test/AOJ/2706.test.cpp)

• View this file on GitHub
• Last update: 2024-06-30 19:07:00+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2706

$0$ 以上 $1$ 未満の $b$ 進数の値について考えてみる。 $x = 0.d_{1}d_{2}\dots d_{k}$ だったとき、 $x = \sum_{i = 1}^{k} \frac{d_{i}}{b^{i}}$ である。

これを通分すると $\frac{1}{b^{k}}\sum_{i = 1}^{k} d_{i}\times b^{k - i}$ となる。

結局のところ $\frac{P}{Q}$ の分母が $b^{k}$ の約数となる最小の $b$ を考えれば良い。 $\frac{Q}{\text{gcd}(P, Q)}$ の素因数の積が解となる。

Depends on

• Src/Number/PrimeFactor.hpp
• Src/Number/PrimeFactorize.hpp
• ioまわりの設定 (Src/Template/IOSetting.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2706"

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/Number/PrimeFactorize.hpp"

#include <iostream>
#include <numeric>

using namespace zawa;

int main() {
    SetFastIO(); 
    int P, Q;
    std::cin >> P >> Q;
    Q /= std::gcd(P, Q);
    int ans{1};
    for (const auto& data : PrimeFactorize((unsigned)Q)) {
        ans *= (int)data.factor();
    }
    std::cout << ans << '\n';
}

#line 1 "Test/AOJ/2706.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2706"

#line 2 "Src/Template/IOSetting.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Template/IOSetting.hpp"

#include <iostream>
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

} // namespace zawa
#line 2 "Src/Number/PrimeFactorize.hpp"

#line 2 "Src/Number/PrimeFactor.hpp"

#line 4 "Src/Number/PrimeFactor.hpp"

#include <type_traits>

namespace zawa {

template <class T>
class PrimeFactor {
    static_assert(std::is_unsigned_v<T>, "T must be unsigned integer");
private:
    T factor_{};
    u32 exponent_{};

public: 
    PrimeFactor() = default;

    PrimeFactor(T factor, u32 exponent) : factor_{factor}, exponent_{exponent} {}

    inline T factor() const noexcept {
        return factor_;
    }

    inline u32 exponent() const noexcept {
        return exponent_;
    }

    friend bool operator<(const PrimeFactor<T>& lhs, const PrimeFactor<T>& rhs) {
        return lhs.factor() != rhs.factor() ?
            lhs.factor() < rhs.factor() :
            lhs.exponent() < rhs.exponent();
    }

    friend bool operator>(const PrimeFactor<T>& lhs, const PrimeFactor<T>& rhs) {
        return lhs.factor() != rhs.factor() ?
            lhs.factor() > rhs.factor() :
            lhs.exponent() > rhs.exponent();
    }
};

} // namespace zawa
#line 5 "Src/Number/PrimeFactorize.hpp"

#include <cassert>
#line 8 "Src/Number/PrimeFactorize.hpp"
#include <utility>
#include <vector>

namespace zawa {

template <class T>
std::vector<PrimeFactor<T>> PrimeFactorize(T x) {
    static_assert(std::is_unsigned_v<T>, "T must be unsigned integer");
    assert(x > T{0});
    std::vector<PrimeFactor<T>> res;
    for (T f{2} ; u64{f} * f <= x ; f++) {
        u32 exp{};
        while (x % f == 0) {
            exp++;
            x /= f;
        }
        if (exp) {
            res.emplace_back(f, exp);
        }
    }
    if (x > T{1}) {
        res.emplace_back(x, u32{1});
    }
    return res;
}

} // namespace zawa
#line 5 "Test/AOJ/2706.test.cpp"

#line 7 "Test/AOJ/2706.test.cpp"
#include <numeric>

using namespace zawa;

int main() {
    SetFastIO(); 
    int P, Q;
    std::cin >> P >> Q;
    Q /= std::gcd(P, Q);
    int ans{1};
    for (const auto& data : PrimeFactorize((unsigned)Q)) {
        ans *= (int)data.factor();
    }
    std::cout << ans << '\n';
}

Back to top page