[PAT A1096]1096 Consecutive Factors_综合

[PAT A1096]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.

输入格式

Each input file contains one test case, which gives the integer N (1<N<2?³¹??).

输出格式

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.

输入样例

630

输出样例

3
567

解析

题目的意思很简单，就是输入一个数，输出一串连续的数，使得它们的乘积能被输入的数整除。
我首先想的是，由于是连续的，所以我把1！，2！，3！，4！……存放在数组里面，知道某个数的阶乘大于INT_MAX即可，这样，任意两个数之比就是连续的一串数相乘，例如v[5]=5！，v[3]=3！，那么v[5]/v[3]=4x5，我觉得这是一个不错的方法，但是很可惜的是，由于数组开得过大，导致两组数据超时，所以只拿了17分。，然后也没有想到好的上限，所以就放弃了这种方法。

我第一次做的方法，仅供参考，如果能寻得更好的上界或许能在时间允许范围内完成

#include<iostream>
#include<climits>
#include<cmath>
#include<vector>
using namespace std;
int main()
{
    long long mul = 1, t = 1;int n;scanf("%d", &n);vector<int> v;  //开乘积数组while (mul <= INT_MAX) {
    v.push_back(mul);mul *= ++t;}int left, right, len = 0;for (int i = 0; i < v.size() - 1; i++) {
    for (int j = i + 1; j < v.size(); j++) {
    if ((n % (v[j] / v[i]) == 0) && j - i > len) {
    left = i;right = j;len = right - left;}}}printf("%d\n", len);for (int i = left + 1; i <= right; i++) {
    printf("%d", i + 1);if (i != right) printf("*");}return 0;
}

新的方案就用到了数学思想，首先我们在2到√n之间求解，如果在2到√n之间找到了解，那么该解就是我们要求的解，如果没找到的话，那说明解就是该数本身，为什么呢？因为之前说过，如果一个数能写成多个数相乘的形式，那么要么只有一个数大于√n，要么所有的数都≤√n，因为如果有两个数大于√n，那么他们的乘积就会＞n。
这里程序需要注意的一点就是，乘积必须使用long long类型存储，因为temp是多个数连乘，很有可能会大于int的上限。
另外一点就是，这里按道理说上限是√n，但是我们一旦发现某个连乘不能被整除，那么立即break，一是因为没有执行下去的必要了，二是√n也不小一直执行下去会导致long long也放不下，导致出现浮点错误。

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int n, bound;scanf("%d", &n);bound = (int)sqrt(n*1.0);int len = 0, left, right;for (int i = 2; i <= bound; i++) {
    long long temp = 1;for (int j = i; j <= bound; j++) {
    temp *= j;if (n%temp != 0) break;if (j - i + 1 > len) {
    left = i;right = j;len = j - i + 1;}}}if (len == 0) printf("1\n%d", n);else {
    printf("%d\n", len);for (int i = left; i <= right; i++) {
    printf("%d", i);if (i != right) printf("*");}}return 0;
}

[PAT A1096]1096 Consecutive Factors