PTA团体程序设计天梯赛-练习集 做题笔记

L1-006 连续因子 (20 分)

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

输入格式：

输入在一行中给出一个正整数 N（1<N<231）。

输出格式：

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

输入样例：

630

输出样例：

3
5*6*7

以上是题面

题解

经典的枚举好题
从初学者的角度，本题的难点有：
一、题意理解。此题容易误解成以下情况：
先求出输入的正整数N的全部因子，例如1260的因子有2 3 4 5 6 7 9 10 12 14 15 18 20 21 28 30 35 36…，那么答案就是2*3*4*5*6*7。然而2×3×4×5×6×7=5040>1260 ，很显然是错误的。这是因为题意是将N分解为一串因子，这些因子相乘=N。要满足这个条件，其实也就是我们所求的连续因子的乘积也是N的因子或其本身。

二、如何维护保存我们求的最长最小因子串呢？
第一瞬间想到的或是最低级的方法当然是拿数组存。但仔细想想，我们求得的是一串连续的数字，同时也知道第一个数字的值和这一串数字的个数，即知道了起始地址与偏移量，于是我们只用维护当前最长最小因子的begin和length即可输出整个因子串。

三、需要注意的细节
1、首先是遇到质数的情况。由于我们不输出1因子(N=1除外)，所以遇到质数便输出1 \n N即可；
2、为啥我上面一直要强调最长且最小的因子串呢？因为这看似不起眼的最小其实有点细节嗷，稍不注意这因子串他就不是最小了。具体的位置我会在AC代码中注释出来。

以下是AC代码

/*
 * @Author: 句蒻勾
 * @Date: 2022-01-10 15:42:50
 * @Last Modified by: 句蒻勾
 * @Last Modified time: 2022-01-10 15:42:50
 * @Description: L1-006 连续因子 (20 分)
*/
#include<bits/stdc++.h>
using namespace std;
long long cnt; 
long long max_count;
long long N;
long long start;       //由于之前有个测试点没过我就全部开了longlong XD
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for(int i = 2; i <= sqrt(N); i++){ //注意枚举到sqrt(N)就行了
        int j = i;
        long long temp = N;
        cnt = 0;
        while(temp % j == 0){  
            temp /= j;  
            j++;//这样就可以连续地求因子了
            cnt++;
        }
        if(cnt > max_count){//如果用>=就不是最小因子串了，而是最大，不符合题意
            max_count = cnt;
            start = i;//维护最长
        }
    }
    if(max_count == 0){//质数特判
        cout << 1 << endl;
        cout << N;
    }
    else{
        cout << max_count << endl;
        for(int i = 0; i < max_count; i++){
            cout << start + i;
            if(i != max_count - 1){
                cout << "*";
            }
        }
    }
	return 0;
}