LeetCode #1390. Four Divisors

👉 LeetCode #1390. Four Divisors

問題

原文

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors. If there is no such integer in the array, return 0.

日本語

与えられた nums に対して，4 つの約数を持つ値の約数の和を返せ．ない場合は 0 を返せ．

アプローチ

これは単純に考えると計算が爆発しそうですが，実は簡単な問題に落とし込むことができます．
まず，4 つのうち 2 数がすでに確定しているのは自明です．

それは 1 と n （n in nums）です．（$\because$ 1 と自分は確実に，その値を割り切れる）

つまり，「約数がちょうど 4 個である」という条件は，

残りの 2 つの約数がどのような形で存在するか

を考える問題になります．

ここで，約数の個数は素因数分解によって決まるという事実を利用します．
$n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$ と素因数分解できるとき，
約数の個数は $(e_1+1)(e_2+1)\dots(e_k+1)$ で表されます．

今回の場合，$(e_1+1)(e_2+1)\dots(e_k+1) = 4$を満たす整数の組を探索するということになります．

ここで，左辺を分解してみると，正の整数で 4 を作る方法は

1. $4 = 4$
2. $4 = 2 \times 2$

になります．

それぞれを指数に戻すと，

1. $e_1 + 1 = 4 \Rightarrow e_1 = 3$
   $ \therefore n = p^3$（$p$ は素数）
2. $(e_1+1)(e_2+1) = 4 \Rightarrow (e_1+1)(e_2+1) = 2 \times 2$
   $ e_1 = 1, e_2 = 1$
   $ \therefore n = p \times q (p \neq q )$（$p \neq q$, $p,q$ は素数）

以上より，「約数がちょうど 4 個である」数は，
$n = p^3$（$p$ は素数） または $n = p \times q$（$p \neq q$, $p,q$ は素数） のいずれかに限られます．

上記のいずれかを満たす値の約数の総和が答えになります．

実装

上記を満たす値を求めるコードを実装します．
Python での実装は下記になります．

class Solution:
    def sumFourDivisors(self, nums: List[int]) -> int:
        def is_prime(n):
            if n < 2:
                return False
            for i in range(2, int(pow(n, 1/2))+1):
                if n % i == 0:
                    return False
            return True
        
        ans = 0
        for n in nums:
            # 1. p ** 3 -> (1, p, p * p, n)
            p = round(pow(n, 1/3))
            if p**3 == n and is_prime(p):
                ans += 1 + p + p*p + n
                continue
            
            # 2. p*q -> (1, p, q, n)
            for p in range(2, int(pow(n, 1/2))+1):
                if n % p == 0:
                    q = n // p
                    if p != q and is_prime(p) and is_prime(q):
                        ans += 1 + p + q + n
                    break
        return ans

さいごに

今回も知っていたら（気づけば）割と簡単に解ける問題を紹介しました．
数学的な問題は忘れている知識も多いので難しいですね！
問題パターン整理しておきたいですね！