SRM 599(div1) Easy: BigFatInteger

Twitterに潜っていたらプロからこんな発言が。

C が難しいという方は SRM 401 - 600 の Div1 Easy 200本ノック辺りをやれば瞬殺できるようになると思います（適当）

— えびま (@evima0) 2018年7月7日

よし、やってやろうじゃないか（錯乱）
ってことで1問目。なんか回数によってアクセスに無限に時間がかかるので、適当に出来るところからやってきます。

問題

X=1を以下の操作のどちらかを選んで適用することを繰り返して、A^Bを作りたいです。最小の操作回数を求めてください。

• ある素数pを選択して、X*=pとする
• Xを割り切ることが出来る数dを1つ選んで、X*=dとする

解説

取り敢えず考えたのが、「Aを作る→B乗する」という考え方。

Aを最初に作るのですが、素因数分解して、各素因数毎にAに必要な乗数だけ操作②を行います。ビット累乗のやつです。ここで重要なのは「一番上のビットまで繰り返した後、それ以外のビットが立っているなら+1で全部埋められる」という考察です。
例えばn¹⁵をnから作りたいとして、n⁸まで行ったらn⁷で割り切れるので、一発でn¹⁵が作れます。

また、この操作②はまとめて行うことが出来るので、Aを作るのに必要な操作②は必要な最大値のみを記録します。Aが出来ました。B乗するのは今までの考察から簡単！解けた！

と思ってました。system testでWA。

ということで落とされた例を見てみると、A=2¹⁴、B=59万くらい。14とBをかけてまとめて計算できるのです。
つまり、最初のAの素因数分解で各素因数何乗する必要があるか出ると思うのですが、この時にBをかけてあげて最初からA^Bを目指します。恐らくintに収まるけど怖いのでllで殴る。他は同じ感じです。

で無事AC

struct BigFatInteger
{
    int A;
    ll B;
    int minOperations(int _A, int _B)
    {
        A = _A, B = _B;
        int factnum = 0, factcnt = 0;
        for (int i = 2; i <= A; i++)
        {
            if (A % i == 0)
            {
                factnum++;
                int tmpcnt = 0;
                while (A % i == 0)
                {
                    tmpcnt++;
                    A /= i;
                }
                ll require = tmpcnt * B;
                cout << i << " " << require << endl;
                ll tmpnum = 1;
                int cnt = 0;
                while (require >= tmpnum * 2)
                {
                    tmpnum <<= 1;
                    cnt++;
                }
                factcnt = max(factcnt, cnt + (int)min(1LL, require - tmpnum));
            }
        }
        return factnum + factcnt;
    }
};

感想

初っ端からこれ大丈夫ですかね…？

実際何問が解ける状態（挑戦できる状態）なのか分かりませんが、頑張ります！（因みにこの記事は酔っ払いの状態で書いているので情報が正確であることを保証しません）