はまやんはまやんはまやん

hamayanhamayan's blog

Disjoint Set of Common Divisors [AtCoder Beginner Contest 142 D]

https://atcoder.jp/contests/abc142/tasks/abc142_d

前提知識

解説

https://atcoder.jp/contests/abc142/submissions/7771060

AもBの公約数を列挙する。
といっても、公約数は最大公約数の約数となるので、とりあえず、最大公約数を求める。
互いに素であるということは、同じ素数を使っていないということになる。
つまり、最大公約数を素因数分解したときに、構成される素数の個数分分けるのが最適になる。
なので、素因数分解をして、その個数を求めたら答え。

ll A, B;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B;
    auto ep = enumpr(gcd(A, B));
    int ans = ep.size() + 1;
    cout << ans << endl;
}