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