PAT-L1-006. 连续因子（思维）

L1-006. 连续因子

时间限制

400 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

一个正整数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

非常有意思的题目;

题目让找出len个连续的数字相乘是n的约数。根据n的范围，我们可知道，len的长度至多为12，因为（13!)>2^31;

所以，我们从最长的情况开始暴力。当len个连续数字相乘是n的约数的话，就说明找到了正确答案。当循环结束之后仍未找到，说明n是个质数。特判一下。

#include<bits/stdc++.h>
using namespace std;

const int MAX = +;
const int INF = ;


int main(){
    int n;
    scanf("%d",&n);
    int flag=;
    for(int len=;len>=;len--){//len个连续数字相成
        int start = ;//起始数字为2
        for(int j = start;j<=sqrt(n);j++){//其实数字从2--sqrt（n），的各种情况
            int temp=;
            for(int k = ;k<len;k++){
                temp*=(j+k);
            }
            if(n%temp==){//如果乘积是n的约数，说明找到了答案，输出。
                flag=;
                printf("%d\n",len);
                for(int s = j;s<j+len-;s++){
                    printf("%d*",s);
                }
                printf("%d\n",j+len-);
                return ;//找到了，所以跳出
            }
        }
    }
    if(flag==){//没有找到，说明n是一个质数，输出1\n1
        printf("%d\n%d",,n);
    }
    return ;
}