ABC169のD問題に挑戦してみた - インフラエンジニアの備忘録とか色々

初めに

今回はABC169のD問題に挑戦してみました。
この問題は、方針は浮かんだのですが実装が出来ませんでしたが、
今まで書いた事が無い手法だったので、今回はABC169のD問題について書きます。

※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。

D - Div Game

ある整数Nが与えられ、下記の操作が最大で何回行えるかを求める問題です。

f:id:hgm_blog:20200927155743p:plain — 引用

最終的な回答

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const long long INF = 1LL<<60;

typedef pair<ll,ll> Pair;
int main(){

ll N;

cin >> N;

vector<Pair> fs;

for(ll i = 2;i*i <= N;++i ){

    ll cnt = 0;

    //素因数分解
    //割り切れなくなるまで割り算を行う
    while(N%i==0){
        //割り算を行える回数をカウント
        N/=i;
        ++cnt;
    }
        //素因数の数をそれぞれ個数を格納
        fs.emplace_back(i,cnt);
}

// Nの値が1ではなかった場合はその数は素因数となるため格納
if(N!=1) fs.emplace_back(N,1);

ll ans = 0;

for(Pair p : fs){

    
    ll cnt = p.second;
    ll x = 1;
    // 
    while(x <= cnt){
        cnt -= x;
        ++ans;
        ++x;
    }
}

cout << ans << endl;

return 0;

}

まずは、試しに例題として記載されているN=24のパターンで素因数分解してみると、
素因数は2が3つ、3が1つあることがわかります。

今回の問題では最大何回の操作が行えるかを求める問題であり、以下のように
小さい素因数から指数の小さい順に操作を行う事で操作回数が最大になります。

f:id:hgm_blog:20201003224059p:plain — イメージ

素因数分解については、2から $\sqrt{N}$ までの整数で計算を行う事で求められます。
プログラム上では $i*i \leq N$ という条件でループを行っています。(下記参照)

f:id:hgm_blog:20201003224810p:plain — イメージ

2から $\sqrt{N}$ までで良い理由としては、下記のようにNをある数で割りきれた場合、
計算結果から得られた商でも割り切る事が可能であり、 $\sqrt{N}$ 以降の値での割り算は
すでに2から $\sqrt{N}$ の範囲で計算したものと同様であるためです。

f:id:hgm_blog:20201003230738p:plain — イメージ

※ちゃんとした証明はけんちょんさんのブログ↓を見た方が良いです。 https://qiita.com/drken/items/a14e9af0ca2d857dad23

素因数分解が完了したら、あとは求めた素因数の個数を1,2,3....という形で引いていき、
その回数を集計することで最大回数を求める事が出来ます。

最後に

今回の素数判定の計算量削減のようなテクニックは演習を重ねてどんどん身に着けて
行きたいですね。今までもテクニックとして見たことはあったんですが、
あまり理解していなかったのでブログを書くことで理解が深まって良かったです。