聪明的燕姿
现在已知一个s
让你求x
什么样的x呢?
x的所有约数的和为s
$x={p_1}^{c_1} \times {p_2}^{c_2} \times {p_3}^{c_3} ... $
$s={({p_1}^{0} + {p_1}^{1} ... + {p_1}^{c_1}) \times ({p_2}^{0} + {p_2}^{1} ... + {p_2}^{c_2})} \times ...$
观察上式,我们可以得出结论 $ x < s $,即使是最接近的情况也是 $s-1=x $,当为这种情况时
$s-1 == x == p \leftarrow ( * )$
除了上述情况其他情况都是:
$s > x > p^2$
因此,我们写出dfs如下:
void dfs(int u,int prod,int v)
{
if (v == 1)
{
res[len++] = prod;
return;
}
if (v - 1 > ((u < 0) ? 0 : primes[u]) && is_prime(v - 1))
{
res[len++] = prod * (v - 1);
}
for (int i = u + 1; primes[i] <= v / primes[i] ; i++)
{
int p = primes[i];
for (int t = p + 1, k = p;t <= s; k *= p, t += k)
{
if (v % t == 0)
{
dfs(i, prod * k, v / t);
}
}
}
}
其中u代表上一次遍历到的素数的编号,prod代表在上一个素数中算到的x的大小,v代表上一次的s的大小
如果v==1,代表s在历次dfs中被除尽了,那我们就将此刻的x写入到res中
由于除了 ( * )式外其他的因子 $p \leqslant v$ (由于x的不确定的故用v)
故将 ( * )式特殊判断
首先判断是不是( * )的方法很简单哈,需要满足两个条件:
- 在这个dfs中的因子一定是要大于之前的因子的,而之前的最大的因子是primes[u],而当前要检验的因子是v-1,故需要v-1>primes[u],但是有一个问题,如果是第一次进入dfs它的上一次因子是没有啊,所以此时的上一次因子就设为0,故有
v - 1 > ((u < 0) ? 0 : primes[u])
- 所有的因子一定是素数,所以还需要判断素数
满足这两个条件就可以将其纳入res中了,x就是这次的因子乘上之前的因子的连乘,即
res[len++] = prod * (v - 1);
至于这里为什么不return原因在于
此时prod = x = p // p表示素数
同时v = s = 1 + p
而你要求的是 v 能不能在接下来的双循环中被某一个t所除,而此时v = 1 + p,v不一定为素数,故还有被除的机会