abc169_d Div Gameの解き方の解説
2020/06/01 13:06
感謝の正拳突き１万回ならぬ、競プロサイトで 1 日 1AC(正解)するように頑張る。
ABC169 の D 問題 Div Gameを解いていきます。
問題文の読解力問題なような気がしました。
入力例 1,出力例 1 をよく読む
よく読むと、2 の 1 乗で 1 回、2 の 2 乗で 2 回、3 の 1 乗で 1 回割れることがわかります。つまり素因数分解した結果から 1 回、2 回、3 回と割る数を増やしていって、何回操作できるかという問題です。
素因数分解
素因数分解はプログラミングでよく題材になります。素因数分解 C++などで検索するとたくさん参考になるアルゴリズムが出てくるので、参考にさせてもらいましょう。
できあがり
#include <bits/stdc++.h>
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 n,result;
int main() {
cin >> n;
for(auto&& x : prime(n)) {
int i = x.second, cnt = 1;
while(true) {
if(i >= cnt) {
result++;
i -= cnt;
cnt++;
} else {
break;
}
}
}
cout << result;
}