1096. Consecutive Factors.md

【PAT A-1096】Consecutive Factors

题意概述

在正整数N的所有因子中，可能存在几个连续的数字。例如，630可以分解为3×5×6×7，其中5、6和7是三个连续的数字。现在给定任何正数N，您应该找到最大数量的连续因子，并列出连续因子的最小序列。

输入输出格式

输入在一行给出正整数N。

对于每个测试用例，请在第一行中打印最大连续因子数。然后在第二行中，以格式factor [1] * factor [2] * ... * factor [k]来打印连续因子的最小序列，其中因子以升序排列，注意，因子中不应包含1。

数据规模

$$0<N<2^{31}$$

算法设计

暴力枚举即可。对于$\left[2,\sqrt n\right]$中每一个N的因子i，去枚举以i为首因子的连续因子，找出长度最长的因子序列即可。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni;
    cin >> ni;
    gg num = 1, first = ni;
    for (gg i = 2; i <= (gg)sqrt(ni); ++i) {
        if (ni % i == 0) {
            gg n = ni, curnum = 0;
            for (gg j = i; n % j == 0; ++j) {
                n /= j;
                ++curnum;
            }
            if (curnum > num or (curnum == num and first > i)) {
                num = curnum;
                first = i;
            }
        }
    }
    cout << num << "\n";
    for (gg i = 0; i < num; ++i) {
        cout << (i == 0 ? "" : "*") << first + i;
    }
    return 0;
}