B 問題が結構大変なのに比べて C 問題は毎度穏やかな感じ

問題概要

整数 $N$ が与えられる。これを使ってゲームをする。

$N$ の真の約数の中から整数を 1 つ宣言する、ただしこのとき既に宣言したことのある整数の約数になるものは宣言できない
宣言できる整数がある限りこれを繰り返す

ゲームを終了させるまでに行われる宣言の回数としてあり得る値の最小値と最大値を求めよ。

制約

$1 \le N \le 10^{12}$

考えたこと

最大値の方が簡単で、 $N$ の約数を $N$ を除いてすべて小さい順に並べていけばよいので、 $N$ の約数の個数 -1 が答え

最小値の方も実は簡単で、例えば

$N = 2^{5} × 3 × 5^{3}$

とかだったとき、最低でも各素因子について指数を 1 個ずつ減らした

$N = 2^{4} × 3 × 5^{3}$
$N = 2^{5} × 5^{3}$
$N = 2^{5} × 3 × 5^{2}$

たちはどの 2 つも同時に潰すことはできないので、最低でも「素因子の個数」だけの回数は必要であることがわかる。逆に上の宣言を行うと、もういかなる $N$ の約数も宣言できなくなるので、これが最小値である。

まとめると

最大値： $N$ の約数の個数 - 1
最小値： $N$ の素因子の個数

となる。

#include <iostream>
using namespace std;

int main() {
    long long N; cin >> N;
    long long mi = 0, ma = 1;
    for (long long p = 2; p * p <= N; ++p) {
        if (N % p != 0) continue;
        int num = 0;
        while (N % p == 0) {
            N /= p;
            ++num;
        }
        ++mi;
        ma *= (num + 1);
    }
    if (N != 1) {
        ++mi;
        ma *= 2;
    }
    cout << mi << " " << ma-1 << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2932 約数ゲーム (RUPC 2019 day3-C)

問題概要

制約

考えたこと