PAT_甲级_1096 Consecutive Factors (20point(s)) (C++)【分解因子/优美暴力】

 

1，题目描述

• consecutive：连续不断的； 

Sample Input:

630

 

Sample Output:

3
5*6*7

题目大意

 输出一个数N，最长连续因子的长度，及最早出现此长度的因子序列；

注意

• print in the first line the maximum number of consecutive factors：连续因子的最大长度；
• print the smallest sequence of the consecutive factors：打印连续因子的最小序列（这句话的意思不是很清楚，可能是最大长度的连续因子不唯一时，输出较小的那个吧）；
• x = INT_MAX，x-pow(2, 31)=-1：int类型足够表示N；
• 1 is NOT included：因子1不输出，即若N为质数，则连续因子部分只输出N；

 

2，思路

参考大神@日沉云起【pat甲级1096. Consecutive Factors (20)】

优雅的暴力解法：（实测有效）

1. 设计fun函数，返回从参数i开始的连续因子个数；
2. i从2遍历到sqrt(N)，对每个i调用一次fun函数，并更新最长连续因子：
3. 当N为质数时特殊处理：

 

3，AC代码

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

int fun(int i, int num){
    int len = 0;
    while(num % i == 0){
        num /= i;
        i++;
        len++;
    }
    return len;//若num为质数 则输出len为0
}
int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int N;
    cin>>N;
    int num = N, first = 0, maxLen = 0;//first连续因子的第一个因子 maxLen最长连续因子
    for(int i = 2; i <= sqrt(num); i++){
        int len = fun(i, num);
        if(len > maxLen){
            first = i;
            maxLen = len;
        }
    }
    if(maxLen == 0){
        printf("1\n%d", N);
        return 0;
    }
    printf("%d\n%d", maxLen, first);
    for(int i = 1; i < maxLen; i++)
        cout<<'*'<<first+i;
    return 0;
}

 

4，解题过程

第一搏

想将所有因子存入map<int, int>中，然后再排列组和，但是怎么排序没想出来。。。

之后又有一些其他想法，都行不通。。。╥﹏╥...

只好欣赏大神的解法了

---------------------------------------------------------------------------------------------------------------

优雅的暴力解法：对于2~根号N中每一个N的因子i，去枚举以i为首因子满足乘积能整除N的连续因子，如果比当前最长因子数大，更新最长因子数和相关第一个因子；（简单粗暴且有效！）

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

int fun(int i, int num){
    int len = 0;
    while(num % i == 0){
        num /= i;
        i++;
        len++;

    }
    return len;
}
int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int N;
    cin>>N;
    int num = N, first = 0, maxLen = 0;//first连续因子的第一个因子 maxLen最长连续因子
    for(int i = 2; i <= sqrt(num); i++){
        int len = fun(i, num);
        if(len > maxLen){
            first = i;
            maxLen = len;
        }
    }
    cout<<maxLen<<endl;
    cout<<first;
    for(int i = 1; i < maxLen; i++)
        cout<<'*'<<first+i;
    return 0;
}

从时间复杂度来看，而且20分拿到了18分，完全可行！接下来只需要考虑特殊情况了。

第二搏

测试：当输入为质数时，

大佬也提出了这一点，所以当输入为质数时，maxLen为0，特殊处理即可：

贼稳！o(*￣▽￣*)ブ