AtCoder

ABC280 D問題(Factorial and Multiple)を解く

AtCoder_ABC280_D

AtCoder が提供しているABC(AtCoder Beginner Contest)280 のD問題をC++とPythonで解いてみました。ABC280は、2022年12月3日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Factorial and Multiple(Difficulty : 880)

問題はリンク先をご覧ください。

ABC280 D問題 Factorial and Multiple

与えられた数字を素因数分解をして、解答を求めます。AtCoder Problems による Difficulty は、880 でした。ABC D問題として、標準的な問題です。

解答案

素朴に考えると、K の倍数となるような N! を計算すればよいと思うかもしれません。ただし、N! は非常に速く大きくなります。このため階乗の記号が ! になっているという人もいます。

例えば、入力例2にある 123456789011 の解答は、123456789011 の階乗になりますが、これは、Project Euler 問題20で紹介したスターリングの公式を使うと、1013 桁の数になることが分かります。とても計算できる大きさではありません。

入力例2の 123456789011 が素数であることに気づくと、素因数分解を使うことが分かります。

素因数分解を行う関数

素因数分解は、Project Euler 問題3で考察しました。$\sqrt{n}$ まで調べれば効率良く素因数分解ができることが分かりました。

素因数分解は関数として独立させることにします。関数名や戻り値に map を使うことも含めて、「蟻本」(「プログラミングコンテストチャレンジブック」第2版 秋葉拓哉、岩田陽一、北川宣稔著、マイナビ 2012年)を参考にしました。

以下が関数 prime_factor の実装例です。

typedef unsigned long long int ull;

map<ull, ull> prime_factor(ull n)
{
	map<ull, ull> result;

	for (ull i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			++result[i];
			n /= i;
		}
	}
	if (n != 1) {
		result[n] = 1;
	}

	return result;
}

次に考えること

問題に掲載されている3つの入力例と出力例(解答)を振り返ります。

  • 入力例1 $30 = 2 \times 3 \times 5$ の解答は、 $5! = 120$
  • 入力例2 $123456789011$ は素数、解答は、$123456789011!$
  • 入力例3 $28 = 2^2 \times 7$ の解答は、$7! = 5040$

この3例だけみると、一番大きな素因数が解答になると勘違いするかもしれませんが、それは間違っています。

  • 入力例4 $12 = 2^2 \times 3$ の解答は、$3! = 6$ ではなく、$4! = 24$ になる。

計算が簡単な2の累乗について、具体的に計算してみましょう。

K最小のN!2を素因数にもつ数
212!2が1個
224!2が1個、4が2個
234!↑に同じ
246!2、6が1個、4が2個
258!2、6が1個、4が2個、8が3個
268!↑に同じ
278!↑に同じ
2810!2、6、10が1個、4が2個、8が3個
2912!2、6、10が1個、4、12が2個、8が3個
21012!↑に同じ
21114!2、6、10、14が1個、4が2個、8が3個

4は、2を2個素因数に持ち、8は、2を3個素因数に持つため、K が増えても N! が増えない場合があることが分かります。

この問題は、特定の素因数をいくつ含むかカウントする問題となります。式で具体的に記します。

$K = b_1^{p_1} b_2^{p_2} \cdots b_m^{p_m}$ と素因数分解できたとします。この場合に、素因数 $b_i$ を $p_i$ 個以上含む最小の $N_i!$ を求める問題となります。

方針

問題を解く方針を書きだします。

  • K を読み込む。
  • K を素因数分解する。$K = b_1^{p_1} b_2^{p_2} \cdots b_m^{p_m}$
  • それぞれの $m$ に対して、以下を求める。
    • 素因数 $b_i$ を $p_i$ 個以上含む最小の $N_i!$ を求める。
  • 最大の $N_i (i = 1, 2, …, m)$ を出力する。

    C++ プログラム例(ABC280D)

    素因数分解をして得られた $b_i^{p_i}$ に対して、$b_i \times n$ が素因数 $b_i$ をいくつ 含むか求めて加えていき、$p_i$ 個以上含むような最小の $(b_i \times n)!$ を求めています。

    以下が、C++の実装例です。

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef unsigned long long int ull;
    
    map<ull, ull> prime_factor(ull n)
    {
    	map<ull, ull> result;
    
    	for (ull i = 2; i * i <= n; ++i) {
    		while (n % i == 0) {
    			++result[i];
    			n /= i;
    		}
    	}
    	if (n != 1) {
    		result[n] = 1;
    	}
    
    	return result;
    }
    
    int main()
    {
    	ull k;
    	cin >> k;
    
    	ull result = 1;
    	map<ull, ull> m;
    
    	m = prime_factor(k);
    	for (auto it = m.begin(); it != m.end(); ++it) {
    		ull b = (*it).first;
    		ull p = (*it).second;
    		ull n = 1;
    		ull p_t = 1;
    		while (p_t < p) {
    			++n;
    			++p_t;
    			ull n_t = n;
    			while (n_t % b == 0) {
    				++p_t;
    				n_t /= b;
    			}
    		}
    		result = max(result, b * n);
    	}
    
    	cout << result << endl;
    
    	return 0;
    }

    AC(Accepted=正しいプログラム)と判定されました。

    Python プログラム例(ABC280D)

    素因数分解する関数は、defaultdict を返しています。基本的に C++ をそのまま置き換えたプログラムです。

    """AtCoder Beginner Contest 280 D"""
    from collections import defaultdict
    
    
    def prime_factor(n):
        factor = defaultdict(int)
        i = 2
        while i * i <= n:
            while n % i == 0:
                factor[i] += 1
                n //= i
            i += 1
        if n != 1:
            factor[n] = 1
        return factor
    
    
    k = int(input())
    result = 1
    m = prime_factor(k)
    for b, p in m.items():
        n = 1
        p_t = 1
        while p_t < p:
            n += 1
            p_t += 1
            n_t = n
            while n_t % b == 0:
                p_t += 1
                n_t //= b
        result = max(result, b * n)
    
    print(result)

    こちらも「AC」と判定されました。

    最後に

    この問題を解くときには、2の累乗の場合を手計算して構造を把握しました。構造が把握できない場合には、簡単な場合に手計算することが有効であることが分かりました。

    ABC280は、B問題とC問題は取り組みやすいと感じました。特にC問題は簡単に感じました。一方、D問題は、手計算で構造を把握して時間内に解くことができました。

    引き続き ABC を解いていきます。

    COMMENT

    メールアドレスが公開されることはありません。 が付いている欄は必須項目です

    CAPTCHA