如何將一個[10^3,10^15]上的整數儘可能多地表示成n個互不相同的因數乘積？

01-04

input 是一個10^3 到10^15 的整數
然後將這個整數儘可能的分成n個互不相同的因數。
n要儘可能的多。
output是n。

原文
You are playing the following simple game with a friend:

The first player picks a positive integer X.

The second player gives a list of k distinct positive integers Y1,…,Yk such that (Y1+1)(Y2+1)?(Yk+1)=X, and gets k points.

Write a program that plays the second player.
我的想法是，首先10^15用long存。
然後從2開始mod，如果結果為0，n++, 然後原始數據除以2

以此類推，直到mod的數大於current 的被測數據的平方根。
然後判斷，如果被測數據大於mod的數，n++。
按照我的演算法，以128為例結果為3，應分為2 4 8 和一個2，但是這個2因為是沒用的，所以最後應該直接乘到8上，所以應該是2 4 16.
但是好像這個演算法是錯的。求幫忙。
之前寫的演算法（已被證明是錯的。）
import java.util.Scanner;
public class Main { static Scanner a = new Scanner(System.in); public static void main(String[] args) { long number = a.nextLong(); int counter = 0; int divide = 2; while (number!=1 divide &< Math.sqrt(number)) { if (number % divide == 0) { number/=divide; counter++; } divide++; } if (number &> divide) { counter++; } System.out.println(counter); }
}

$2*4*8*11*13*17*(11*13*17) = 2*4*11*13*17*22*26*34$

這可能是一道搜索題，演算法大概是先分解因數再branch-and-bound。

不過我想到了一種奇葩的演算法，不知道對不對？

先分解因數，然後把各質因數的指數從小到大排列，形成一個元組。然後從這個元組中一步一步地減去較小的元組（按照分次字典序，即：元組a&<元組b，iff degree(a)&示例如下（分別針對我上面舉的例子和某匿名用戶的p^9*q^34）：

(2,2,2,6) = (0,0,0,1) + (0,0,1,0) + (0,1,0,0) + (1,0,0,0) + (0,0,0,2) + (0,0,1,1) + (0,1,0,1) + (1,0,0,1)


(9, 34) = (0, 1) + (1, 0)

	+ (0, 2) + (1, 1) + (2, 0)

	+ (0, 3) + (1, 2) + (2, 1)

	+ (0, 4) + (1, 3)

	+ (0, 5) + (1, 4)

	+ (0, 6)

+ (0, 2)（剩下的(0,2)合併到最後一個tuple(0,6)中，得到(0,8)）

首先，我不會證明這個複雜度是對的（我覺得有問題）。

然後，我看到叉姐都這樣寫了。

最後，你不妨試試吧。。

https://github.com/ftiasch/mithril/blob/master/2013-06-12/D.cpp

考慮有兩個質因數的情況，即可以分解為 $a^bc^d$ ,此時a與c的值無所謂，我們直接對(b,d)二元組來考慮，事實上我們可以觀察到(b,d)和(d,b)是等價的，所以這個二元組的順序無所謂。

假設我們得到了最多不同因數的分解 $(b_1,d_1),(b_2,d_2)cdots (b_n,d_n)$ ，其中 $b_i=b_j land d_i=d_j ightarrow i=j$

對於這裡面每一個二元組，我們可以映射為一個整數 $f(b_i,d_i)=b_i+d_i*(b*(b+1)/2)$

注意，這是一個可逆映射。所以任何一個整數來說最多只有一個二元組與之對應。對於這個整數的值，我們總共有b*d種選擇。所以原始問題就轉換成了在一個含有b*d個整數的集合中找到最大的一個子集，使得這個子集元素值的總和為 $b+d*(b*(b+1)/2)$ 。看起來類似於子集和問題（雖然當前證明是反的。。。），無能為力了。

對於多個質因數的情況，比雙質因數更難。。。。。。

$2^23^25^27^2$ 按你的演算法是分成 $2*3*5*7*210$ ，事實上可以分成 $2*3*5*7*6*35$

題主的演算法對兩個素因子的數都不成立，考慮 $p^{9}q^{34}$ 這裡 $q$ 遠大於 $p$ 。容易知道題主的方法的結果為： $p*p^2*p^3*pq*p^2q*q^2*cdots *q^6*q^{13}$ 但 $p*p^2*p^3*q*q^2*cdots*q^7*pq*pq^2$ 比它要長。