bzoj 3629

题解

给出数 $n$
记 $f(x)$ 表示 $x$ 的因子和
求出所有 $x$ 使得 $f(x) = n$
考虑 $x = p_1 ^{a_1} * p_2 ^ {a_2} * \cdots * p_k ^ {a_k}$
那么 $f(x) = (1 + p_1 + p_1 ^ 2 + \cdots + p_1 ^ {a_1}) * (1 + p_2 + p_2 ^ 2 + \cdots + p_2 ^ {a_2}) * \cdots * (1 + p_k + p_k ^ 2 + \cdots + p_k ^ {a_k})$
因此可以爆搜枚举 $p, a$

Dfs(Now_result, prime_pos, x_remind) {}

分别表示
1.当前结果，即枚举到的素数的指数次幂的乘积，即 $p_i ^ {a_i}$ 的乘积　
2.当前枚举到的素数位置 首先要求出 1e5 内的素数
3.给出的 $x$ 在枚举了之前的数后还剩多少
对于答案的录入
1.如果 x_remind = 1 ,相当于枚举到了这样一种形式 $() * () * () * p_i ^ 0$, 显然当前 Now_result 可以录入.
2.如果 x_remind - 1 是一个 大于等于 Prime[Prime_pos] 的素数，显然 (x_remind - 1) * Now_result 可以录入
考虑这样的话我们已经枚举到了这样的一种形式 $() * () * () * (p_i + 1)$, 所以还原之前的数就是 $p_i * Now_result$