【PAT甲级 - C++题解】1096 Consecutive Factors

1096 Consecutive Factors

Among all the factors of a positive integer N, there may exist several consecutive numbers. For example, 630 can be factored as 3×5×6×7, where 5, 6, and 7 are the three consecutive numbers. Now given any positive N, you are supposed to find the maximum number of consecutive factors, and list the smallest sequence of the consecutive factors.

Input Specification:

Each input file contains one test case, which gives the integer N (1<N<231).

Output Specification:

For each test case, print in the first line the maximum number of consecutive factors. Then in the second line, print the smallest sequence of the consecutive factors in the format factor[1]*factor[2]*...*factor[k], where the factors are listed in increasing order, and 1 is NOT included.

Sample Input:

630

Sample Output:

3
5*6*7

题意

在一个正整数 N 的所有因子中，可能存在几个连续的数字。

例如，630 可以分解为 3 × 5 × 6 × 7 3×5×6×73×5×6×7 ，其中 5、6、7 是三个连续的数字。

现在给定任意正整数 N ，请你找到最大连续因子数，并列出连续因子的最小序列。

思路

我们可以枚举每一个起点，然后再去从该起点出发找出连续因子。

注意，题目需要输出最长的连续因子，且最长长度下连续因子的起点需要最小。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> res;
    for (int i = 2; i <= n / i; i++)
        if (n % i == 0)    //判断是否为约数
        {
            vector<int> seq;
            //找出连续因子
            for (int m = n, j = i; m % j == 0; j++)
            {
                seq.push_back(j);
                m /= j;
            }
            //更新最长的连续因子
            if (seq.size() > res.size())   res = seq;
        }
    //如果是质数，则直接输出
    if (res.empty()) res.push_back(n);
    //输出结果
    cout << res.size() << endl;
    cout << res[0];
    for (int i = 1; i < res.size(); i++)   cout << "*" << res[i];
    cout << endl;
    return 0;
}