[C++知识库]PAT (Advanced Level) 1096——Consecutive连续的

题目传送门

• 数据范围使用int即可
• 求因数是sqrt级别的复杂度，简单暴力就可以了
• 质数需要特殊处理

我一开始无意识地写出了求因数的代码（每个数单独判断是否可以整除）
但是题目的意思是，这一连串因数需要乘起来
即再计算最长连续因数序列时，需要积累各个因数的影响
a /= (cnt + i);

---

我还想当然的认为，连续因数有这样的性质：若检测过$[a,b]$这个序列，那么之后我们只需要从$b+1$开始检测即可
这是一丁点都错的！
所以我们要对从2到sqrt的每一个数i，都计算以i为起点的最长连续因数序列

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;

int x;

int main()
{
	scanf("%d", &x);
	int cnt = 0;
	int ans_cnt = 0;
	int begin;
	for (int i = 2; i <= sqrt(x);++i) {
		if (x % i == 0) {
			int a = x / i;
			cnt = 1;
			while (a % (cnt + i) == 0) {
				a /= (cnt + i);
				cnt++;
			}
			if (cnt > ans_cnt) {
				ans_cnt = cnt;
				begin = i;
			}
		}
	}
	if (ans_cnt == 0) {
		printf("1\n%d",x);
	}
	else {
		printf("%d\n", ans_cnt); 
		for (int i = 0; i < ans_cnt; ++i) {
			printf("%d", begin + i);
			if (i < ans_cnt - 1) printf("*");
		}
	}
	return 0;
}

阅读世界，共赴山海

423全民读书节，邀你共读