gracias 发表于 2012-1-23 00:26:13

Squarefree 分解

如果知道一个数的分解为n=p_1^{i_1}p_2^{i_2}p_3^{i_3}.....p_n^{i_n},那么怎么快速知道有几种办法可以将他分解为因子都是squarefree的呢?

wayne 发表于 2012-1-23 00:27:39

呵
新年的第一贴啊

gracias 发表于 2012-1-23 00:38:17

:) 这么幸运!看来2012是个好年

gracias 发表于 2012-1-23 01:08:18

我有办法计算出来,但想要高效的办法.我的办法是
f(i_1,i_2,i_3 ....i_n)=f(i_1-1,i_2,i_3...i_n-1)+f(i_1,i_2-1,i_3...i_n-1)+....f(i_1,i_2,i_3....i_n-1)
i_1,i_2,i_3....i_n可以先从大到小排序,但总觉得这样很笨拙.希望各位帮我给个好办法

zeroieme 发表于 2012-1-23 14:53:47

基本向量pi={a1……an}
令pi的和等于n的因子系数向量{i1……in}，并且每个pi中至少有一个ai为奇数。

wayne 发表于 2012-1-26 09:40:40

我对整数分解不甚了解。
论坛里有很多人都特别有经验
页: [1]
查看完整版本: Squarefree 分解