PTA 天梯赛备赛 L1-006 连续因子（20 分）（搜索）

骑猪看日落 2022-12-21 15:00 201阅读 0赞

## 题目描述 ##

L1-006 连续因子 （20 分）

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

## 解题思路 ##

感觉被这个样例导致理解错误了，我原本以为是要输出因子的个数，然后求出连续因子序列，然后通过 `因子的个数*所有连续因子序列` 使得结果和输入的 `N` 相等，完全理解错了…

正确思路：

连续的找因子，对于 `N`，我们每次对它的因子进行整除，如果可以的话，因子就加1，同时长度也加1，最后不能整除后，就返回此时连续因子的长度，同时更新左边最开始的因子。那么迭代之后，我们就能找到最长长度的连续因子序列，然后也能得到连续因子序列的起始值，这样我们最终结果就能得到了。

另外，注意点是，如果长度一直为0，那么代表这个数为素数，那么特判一下，直接输出

1
    N（代表输入的数字）

## 提交代码 ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll n;
    ll dfs(ll n,ll b,ll len){
         //剩余被除数，因子，长度
        if(n%b==0)
            return dfs(n/b,b+1,len+1);
        return len;
    }
    int main(){
        
        ios::sync_with_stdio(0);
        cin.tie(0);
        cin>>n;
        ll len=0;
        ll left=0;
        for(ll i=2;i*i<=n;i++){
        
            if(n%i==0){
        
                ll res = dfs(n,i,0);
                if(res>len){
        
                    len=res;
                    left=i;
                }
            }
        }
        if(len==0)
            cout<<1<<endl<<n<<endl;
        else{
        
            cout<<len<<endl;
            for(ll i=1;i<=len;i++){
        
                if(i==1) cout<<left+i-1;
                else cout<<"*"<<left+i-1;
            }
            cout<<endl;
        }
        return 0;
    }

## 提交结果 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyOTcxOA_size_16_color_FFFFFF_t_70_pic_center][]

学如逆水行舟，不进则退

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyOTcxOA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/81b0605abebf437895994d37bdc9ac9a.png