abc142_d Disjoint Set of Common Divisorsの解き方の解説
2020/06/02 13:06
感謝の正拳突き１万回ならぬ、競プロサイトで 1 日 1AC(正解)するように頑張る。
ABC142 の D 問題 Disjoint Set of Common Divisorsを解いていきます。
これは本当に問題文の読解力問題ですね・・。
問題文をよく読む
公約数とは、互いに素とはという注釈が問題文にあります。この 2 つを合わせると、最大公約数の素因数の性質を表していることに気づきます。ただし素因数には 1 を含みませんが、1 は他の素因数と互いに素です。
最大公約数
最大公約数を計算する関数は C++17 から標準でstd::gcdが使えますが、この問題が対応しているバージョンは C++14 です。gcc には同じように使える std::__gcd が実装されているので、こちらを使用しましょう。
素因数分解
素因数分解はプログラミングでよく題材になります。素因数分解 C++などで検索するとたくさん参考になるアルゴリズムが出てくるので、参考にさせてもらいましょう。
できあがり
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;
using namespace std;
#define ll long long
map<ll, int> prime(ll n) {
map< ll, int > ret;
for(ll i = 2; i * i <= n; i++) {
while(n % i == 0) {
ret[i]++;
n /= i;
}
}
if(n != 1) ret[n] = 1;
return ret;
}
ll a,b;
int main() {
cin >> a >> b;
// 最大公約数を取って、素因数分解して、素因数に含まれない1を足す
cout << prime(__gcd(a, b)).size() + 1;
}