个人练习- PAT甲级-1096 Consecutive Factors

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805370650738688

这题其实没有什么思路。。看网上大神的代码理解后才做出来。

题目大意：给一个数N，将其分解成若干数字相乘，求因式中可能的最长的连续的数字串。

思路：最终就是要找到连续的一串数字相乘，那么想办法确定这串数字但开头start的上下限。下限明显是2，上限则需要一点思考——sqrt(N)+1。实际上从纯数学角度来看maxop<sqrt(N)就行了，但【这是计算机】！！！用int的话就无法保证其继续成立了，所以让上限+1后赋给int。代码中i和j为这串数字的开头与结尾。

另外，这串数字的乘积一定要能被N整除，不然就根本不是一个合法的因式，不考虑。

for (int i = 2; i <= maxop; i++) {
    int j;tmp = 1;for (j = i; j <= maxop; j++) {
    tmp *= j;if (N % tmp != 0)break;}if (j - i > len) {
    len = j - i;start = i;}}

最后得到的start就是这串数字的开头，len就是这串数字的长度，两个数确定一个连续数字串。输出即可。

完整代码

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <map>using namespace std;int main() {
    long int N, tmp;scanf("%ld", &N);int maxop = sqrt(N) + 1;int start = 0, len = 0;for (int i = 2; i <= maxop; i++) {
    int j;tmp = 1;for (j = i; j <= maxop; j++) {
    tmp *= j;if (N % tmp != 0)break;}if (j - i > len) {
    len = j - i;start = i;}}if (start == 0) {
    printf("1\n%ld", N);}else {
    printf("%d\n", len);for (int i = 0; i < len; i++) {
    if (i == 0)printf("%d", start+i);elseprintf("*%d", start+i);}}return 0;
}