今日勉強したことを
つらつらと
logo

abc169_d Div Gameの解き方の解説

2020/06/01 13:06
AtCoder Beginner Contest 169のD問題 Div Gameを解く。

感謝の正拳突き1万回ならぬ、競プロサイトで 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;
}

© 2021 simodake