算法
(素因数分解) $O(\sqrt{N})$
先求出 $A$ 和 $B$ 的最大公因数 $g$,再对 $g$ 进行素因数分解
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::gcd;
using std::pair;
using std::vector;
using ll = long long;
vector<pair<ll, int>> factorize(ll n) {
vector<pair<ll, int>> res;
for (ll i = 2; i * i <= n; ++i) {
if (n % i) continue;
res.emplace_back(i, 0);
while (n % i == 0) {
n /= i;
res.back().second++;
}
}
if (n != 1) res.emplace_back(n, 1);
return res;
}
int main() {
ll a, b;
cin >> a >> b;
ll g = gcd(a, b);
auto f = factorize(g);
int ans = f.size() + 1;
cout << ans << '\n';
return 0;
}