[PTA] 连续因子（C++，数学）

一个正整数 $N$ 的因子中可能存在若干连续的数字。例如 $630$ 可以分解为 $3\times 5\times 6\times 7$，其中 $5$、$6$、$7$ 就是 $3$ 个连续的数字。给定任一正整数 $N$，要求编写程序求出最长连续因子的个数，并输出最小的连续因子序列。

输入格式：

输入在一行中给出一个正整数 $N$（1<N<2311<N<2^{31}1<N<231）。

输出格式：

首先在第 $1$ 行输出最长连续因子的个数；然后在第 $2$ 行中按 因子1*因子2*……*因子k 的格式输出最小的连续因子序列，其中因子按递增顺序输出，$1$ 不算在内。

输入样例：

630

输出样例：

3
5*6*7

解题思路：

想要找出最长的连续因子序列，自然要找出所有的连续因子序列

大致上的思路就是：

（1）先找到一个因子，以此作为起始

（2）接下来不断乘法操作，直到乘积不符合条件

（3）记录结尾数字，找到一个连续因子序列，回到步骤（1）

可行性证明：

如果一个$num$能够分解的最长连续因子序列为n1,n2,...,nmn_1,n_2,...,n_mn1​,n2​,...,nm​，那么必然存在k=numn1∗n2∗...∗nmk=\\frac{num}{n_1*n_2*...*n_m}k=n1​∗n2​∗...∗nm​num​，使得num=n1∗n2∗...∗nm∗knum=n_1*n_2*...*n_m*knum=n1​∗n2​∗...∗nm​∗k

所以找到的连续因子序列符合题意

代码实现如下

for (i = 2; i * i <= num; i++) {if (num % i == 0) {//(1) search for next beginsum = 1;for (j = i; j * sum <= num; j++) {//(2) extend lensum *= j;if (num % sum == 0 && j - i + 1 > max_len) {//(3) updatemax_beg = i;max_len = j - i + 1;}}}
}

由于数据范围是$1$~2312^{31}231，直接枚举必然$TLE$

所以利用因子一定成对出现的性质，我们只枚举到231\\sqrt{2^{31}}231​为止

for (i = 2; i * i <= num; i++) {...
}

可行性证明：

对于一个$num$，如果在num\\sqrt{num}num​之前我们找到的最长连续因子序列长度为$len$

那么在num\\sqrt{num}num​之后一定也存在长度为$len$的连续因子序列

但是由于num\\sqrt{num}num​之后的任意两个数字乘积$\ge num$，所以不符合题意

综上所述，最长连续因子序列一定在num\\sqrt{num}num​之前出现

最后，AC代码如下

#include <stdio.h>
#include <stdlib.h>
const int max_num = 1 << 31 - 1;int main() {int num;scanf("%d", &num);int max_len = 0, max_beg = -1;long long sum, i, j;for (i = 2; i * i <= num; i++) {if (num % i == 0) {//(1) search for next beginsum = 1;for (j = i; j * sum <= num; j++) {//(2) extend lensum *= j;if (num % sum == 0 && j - i + 1 > max_len) {//(3) updatemax_beg = i;max_len = j - i + 1;}}}}if (max_beg == -1) {max_beg = num;max_len = 1;}printf("%d\\n", max_len);int max_end = max_beg + max_len;for (i = max_beg; i < max_end; i++) {if (i == max_beg) printf("%lld", i);else printf("*%lld", i);}printf("\\n");return 0;
}

注意要开long long，否则循环部分会因为爆精度无法停止，导致$TLE$