Tất nhiên, điều đầu tiên cần làm là tìm số nguyên tố chính của số, như bộ phát sáng.Nói
n = p^a * q^b * r^c * ...
Sau đó
- tìm ra phân vùng nhân của
m = n/p^a
- cho
0 <= k <= a, tìm ra các phân vùng nhân của p^k, tương đương với việc tìm kiếm các phân vùng phụ gia của k
- cho mỗi nhân giống phân vùng của
m, tìm tất cả các cách khác nhau để phân phối a-k các yếu tố.210 trong những yếu tố
- kết hợp kết quả 2. và 3.
Đó là thuận lợi để điều trị các phân vùng nhân giống như các danh sách (hoặc bộ) của (số chia, đa) cặp để tránh sản xuất bản sao.
Tôi đã viết mã trong Haskell bởi vì đó là thuận tiện nhất và ngắn gọn về các ngôn ngữ tôi biết điều này loại:
module MultiPart (multiplicativePartitions) where
import Data.List (sort)
import Math.NumberTheory.Primes (factorise)
import Control.Arrow (first)
multiplicativePartitions :: Integer -> [[Integer]]
multiplicativePartitions n
| n < 1 = []
| n == 1 = [[]]
| otherwise = map ((>>= uncurry (flip replicate)) . sort) . pfPartitions $ factorise n
additivePartitions :: Int -> [[(Int,Int)]]
additivePartitions 0 = [[]]
additivePartitions n
| n < 0 = []
| otherwise = aParts n n
where
aParts :: Int -> Int -> [[(Int,Int)]]
aParts 0 _ = [[]]
aParts 1 m = [[(1,m)]]
aParts k m = withK ++ aParts (k-1) m
where
withK = do
let q = m `quot` k
j <- [q,q-1 .. 1]
[(k,j):prt | let r = m - j*k, prt <- aParts (min (k-1) r) r]
countedPartitions :: Int -> Int -> [[(Int,Int)]]
countedPartitions 0 count = [[(0,count)]]
countedPartitions quant count = cbParts quant quant count
where
prep _ 0 = id
prep m j = ((m,j):)
cbParts :: Int -> Int -> Int -> [[(Int,Int)]]
cbParts q 0 c
| q == 0 = if c == 0 then [[]] else [[(0,c)]]
| otherwise = error "Oops"
cbParts q 1 c
| c < q = [] -- should never happen
| c == q = [[(1,c)]]
| otherwise = [[(1,q),(0,c-q)]]
cbParts q m c = do
let lo = max 0 $ q - c*(m-1)
hi = q `quot` m
j <- [lo .. hi]
let r = q - j*m
m' = min (m-1) r
map (prep m j) $ cbParts r m' (c-j)
primePowerPartitions :: Integer -> Int -> [[(Integer,Int)]]
primePowerPartitions p e = map (map (first (p^))) $ additivePartitions e
distOne :: Integer -> Int -> Integer -> Int -> [[(Integer,Int)]]
distOne _ 0 d k = [[(d,k)]]
distOne p e d k = do
cap <- countedPartitions e k
return $ [(p^i*d,m) | (i,m) <- cap]
distribute :: Integer -> Int -> [(Integer,Int)] -> [[(Integer,Int)]]
distribute _ 0 xs = [xs]
distribute p e [(d,k)] = distOne p e d k
distribute p e ((d,k):dks) = do
j <- [0 .. e]
dps <- distOne p j d k
ys <- distribute p (e-j) dks
return $ dps ++ ys
distribute _ _ [] = []
pfPartitions :: [(Integer,Int)] -> [[(Integer,Int)]]
pfPartitions [] = [[]]
pfPartitions [(p,e)] = primePowerPartitions p e
pfPartitions ((p,e):pps) = do
cop <- pfPartitions pps
k <- [0 .. e]
ppp <- primePowerPartitions p k
mix <- distribute p (e-k) cop
return (ppp ++ mix)
Nó không đặc biệt tối ưu hóa, nhưng nó không được công việc.
Một số lần và kết quả:
Prelude MultiPart> length $ multiplicativePartitions $ 10^10
59521
(0.03 secs, 53535264 bytes)
Prelude MultiPart> length $ multiplicativePartitions $ 10^11
151958
(0.11 secs, 125850200 bytes)
Prelude MultiPart> length $ multiplicativePartitions $ 10^12
379693
(0.26 secs, 296844616 bytes)
Prelude MultiPart> length $ multiplicativePartitions $ product [2 .. 10]
70520
(0.07 secs, 72786128 bytes)
Prelude MultiPart> length $ multiplicativePartitions $ product [2 .. 11]
425240
(0.36 secs, 460094808 bytes)
Prelude MultiPart> length $ multiplicativePartitions $ product [2 .. 12]
2787810
(2.06 secs, 2572962320 bytes)
Các 10^k là tất nhiên đặc biệt dễ dàng vì chỉ có hai số nguyên tố liên quan (nhưng số squarefree vẫn còn dễ dàng hơn), các thừa được chậm trước đó. Tôi nghĩ rằng bằng cách tổ chức cẩn thận thứ tự và lựa chọn cấu trúc dữ liệu tốt hơn danh sách, có một chút để đạt được (có lẽ một nên sắp xếp các yếu tố chính theo số mũ, nhưng tôi không biết liệu có nên bắt đầu với số mũ cao nhất hay không thấp nhất).
Với phiếu bầu, lý tưởng nên có một số giải thích về lý do tại sao bạn nghĩ rằng điều này cần phải được đóng lại, để OP có thể sửa chữa sai lầm của mình (nếu có). Người bầu cử gần như có thể nói chuyện được không? – TCSGrad
Đóng phiếu bầu mà không có bất kỳ giải thích nào - luôn yêu thích những người đó! – TCSGrad
Tôi bỏ phiếu kết thúc do lỗi. Lời xin lỗi của tôi. –