PTA 团队天梯赛║L1-006 连续因子

一、题目要求

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

输入格式：

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

输出格式：

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

输入样例：

输出样例：

1
2

3
5*6*7

二、解题思路

根据 N 的值的取值范围小于等于 2³¹，而这个值介于 12 的阶乘到 13 的阶乘之间，所以我们可以得到最大的值应该是 12 个数连续相乘，又因为 1 不计算在内，所以最多只要有 11 为连续因子即可。

用暴力的思想，我从 2、3、4…sqrt(N) 开始乘，连着乘以 11 位，10 位，9 位…以此类推。

即连续乘 11 位：

2 3 4 5 6 7 8 9 10 11 12 相乘

3 4 5 6 7 8 9 10 11 12 13 相乘

…

连续乘 10 位：

2 3 4 5 6 7 8 9 10 11 相乘

3 4 5 6 7 8 9 10 11 12 相乘

…

直到只有 1 位时，过程中只要有一个乘积 S 使得 N%S==0，就可以认为找到了连续因子。

为了优化代码，在每次乘的时候如果当前的乘积已经大于 N 了，就没有继续乘的必要了。

三、代码

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int N;
    cin >> N;
    int n = sqrt(N);
    int i, j;
    bool flag = false;
    long long int sum;  //注意数据类型！！
    for(int len=11; len>0; len--)   //用 len 控制连续因子个数，N 最多只能到 12 阶乘
    {
        for(i=2; i<=n; i++) //连续因子不包括 1，从 2 开始乘，最多乘到 N 的开方就足够
        {
            sum = 1;
            for(j=i; j<len+i; j++)    //从当前的 i 开始，乘以的个数为 len 的长度
            {
                sum*=j;
                if(sum>N) break;    //到这就没有必要往下算了
            }
            if(N%sum==0)    //当前的 sum 值是 N 的一个因子
            {
                cout << len << endl << i;
                for(int k=i+1; k<j; k++)
                {
                    cout << "*" << k;
                }
                cout << endl;
                flag = true;
            }
            if(flag) break;
        }
        if(flag) break;
    }

    return 0;
}