Codeforces Round #615 C. Product of Three Numbers

こういう問題を瞬殺できるようにならないといけない。(20分かかったけど気持ち5分くらいで解きたい)

概要

• nが与えられる。積がnとなる異なる$a,b,c$があるならば答えよ。ただし、それぞれ2以上の整数である。

例

積という時点で素因数分解した数の組み合わせという推察はできる。
- 64 ⇒可能 2*4*8
- 32 ⇒不可能 (2*2*2*2*2のため、どうやっても2か4が被る)
- 97 ⇒不可能(素数)

アプローチ

nは高々$10^{9}$なので、$2^{30}$以下である。ということは素因数は高々30であるので、総当たりする。
- 素因数分解する
- この数が2以下の場合は条件を満たせない。
- 素因数を適当に3つに分けて掛け算し、違う3つの数ができたらYESとして答えに採用

WORSTでも30*30*30 = 9000程度なので、力づくで試行した。

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            for j in range(cnt):
                arr.append(i)

    if temp != 1:
        arr.append(temp)

    if arr == []:
        arr.append(n)

    return arr
n = int(input())
for _ in range(n):
    x = int(input())
    dat = factorization(x)
    datlen = len(dat)
    if len(dat) <= 2:
        print("NO")
    else:
        f = False
        a = 1
        for i in range(datlen):
            a *= dat[i]
            b = 1
            for j in range(i+1, datlen):
                b *= dat[j]
                c = 1
                for k in range(j+1, datlen):
                    c *= dat[k]
                if a != b and b != c and a != c and a != 1 and b != 1 and c != 1:
                    f = True
                    break
            if f:
                break
        if f:
            print("YES")
            print("{0} {1} {2}".format(a, b, c))
        else:
            print("NO")