[PAT解题报告] Consecutive Factors
简单题，求n的连续约数，比如n = 630 = 3 * 5 * 6 * 7, 而5,6,7是连续的，所以输出5 6
7。抽象描述是，给定n，求n % (start * (start + 1) * (start + 2) * ... * (start +
len - 1)) == 0的len最长的start。如果有多个start要最小，并且1不能算。
先简单考虑一下，len最长有多长？
给定的范围是int,我们发现12!是不超过int的最大值，所以len最大才是11,即从2乘到12。（其他的11个数乘积比这个还要大）。
如果start >= sqrt(n), 则len = 1，因为start * (start + 1) >
n了，所以不可能了。
于是我们枚举start只要枚举到sqrt(n)就可以了。我们就直接枚举start，然后计算出最长的len，根据刚才的分析start是sqrt(n)，而len最长不过11，所以时间复杂度是11
* sqrt(n)最有， n是2^31，这个复杂度可以接受——而且len缩减很快的。
另外要注意，当结果是1的时候，因为我们希望start尽可能小，对一般的合数一定有一个不超过sqrt(n)的约数，所以我们肯定能取到这个数，比如n
= 21，我们肯定能取到start = 3，结果是len = 1。而当n是质数的时候，len = 1，
而且结果只能是n本身，这点比较特殊。不过没关系，我们预先设定最好的len是0，最后循环结束发现len真的是0，即没找到解，这就说明n是质数了——因为如果有一个小于sqrt(n)的约数,len至少会被更新到1,这时我们设定len
= 1, start = n即可。
其实这个题本质就是一个质数判断的变种，只是当发现一个约数x的时候，我们顺着去找x + 1, x + 2……即可。
代码:
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int getLen(int n, int x) {
int len;
for (len = 0; n % (x + len) == 0; n /= (x + len++))
;
return len;
}
int main() {
int n;
scanf("%d",&n);
int len = 0;
int start = 0;
for (int i = 2; n / i >= i; ++i) {
int may = getLen(n, i);
if (may > len) {
start = i;
len = may;
}
}
if (len == 0) {
start = n;
len = 1;
}
printf("%d\n",len);
for (int i = 0; i < len; ++i) {
if (i) {
putchar('*');
}
printf("%d", start + i);
}
puts("");
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1096
顺丰集团工作强度 428人发布
查看1道真题和解析