AtCoder Beginner Contest D - Div Game
問題はこちら
回答
素数のべき乗でNを割っていくため、まず素因数分解が必要なことが分かる
その上で、素因数分解の結果、素数毎の個数が求まるため、全て異なる数で分割した時の分割数の最大値を求めればいい
分割数の最大値なため、分割単位数の最小値1から始めて行き、分割単位数をインクリメントしていき、徐々に大きい数で分割していく
注意点は以下
2,2,2,2,2,2,2を分割する時、2|2,2|2,2,2|2となり、最後の1つだけ余る
最後の1つに関しては、直前の分割数3の区画に組み込み、2|2,2|2,2,2,2と分割すると考えればいい
素因数分解の実装方法、素数判定法を学習できた
#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>
std::vector<std::pair<long long, long long>> prime;
long long N;
int main()
{
std::cin.tie(0);
std::ios::sync_with_stdio(false);
std::cin >> N;
// 素因数分解 2~√N
for (long long i = 2; i * i <= N; i++) {
if (N % i != 0) {
continue;
}
long long exp = 0;
while (N % i == 0) {
N /= i;
exp++;
}
prime.push_back({i, exp});
}
if (N != 1) {
prime.push_back({ N, 1 });
}
long long ans = 0;
for (const std::pair<long long, long long>& e : prime) {
long long count = e.second;
long long subV = 1;
// 1,2,3...と引いていく
while (true) {
count -= subV;
if (count < 0) {
break;
}
subV++;
ans++;
}
}
std::cout << ans << std::endl;
return 0;
}