【PTA天梯赛】L1-006 连续因子（20分）

作者：指针不指南吗
专栏：算法刷题

🐾或许会很慢，但是不可以停下来🐾

题目

题目链接

题解

题意

求解n的最长连续因子
和因子再相乘的积无关，真给绕进去了

步骤

双重循环，外层表示起点，内层用来寻找连续因子的最大长度
内层循环：temp=n 不断除以j++

代码从输入的整数 n 中寻找最长的连续因子序列。通过遍历从 2 到 $\sqrt{n}$ 的所有整数，尝试每个整数作为连续因子序列的起点。对于每个起点，逐个检查是否能连续整除 n 并记录因子个数。如果找到的连续因子个数超过之前记录的最大值，则更新最长序列的起点和长度。最后，根据找到的最长连续因子序列输出结果，如果没有找到，则输出 1 和 n 本身。

#include<bits/stdc++.h>
using namespace std;int main(){int n;cin>>n;int res=0;int l=1;for(int i=2;i<=sqrt(n);i++){int temp=n;int cnt=0;  //这里看准确是cnt=0int start=i;for(int j=i;temp%j==0&&temp!=0;j++){ //求连续因数temp/=j;cnt++;}//更新答案if(res<cnt){res=cnt;l=start;//cout<<res<<endl;}}// l=start;if(res==0){cout<<1<<endl<<n;return 0;}cout<<res<<endl<<l;for(int i=l+1;i<=l+res-1;i++){cout<<"*"<<i;}return 0;
}

总结

真烧脑，断断续续做了一天
刚开始题目就理解错了，就开始写题

1. 连续因子的求解get到了

for(int j=i;temp%j==0&&temp!=0;j++){ //求连续因数temp/=j;cnt++;}

3. cnt初始化是0
4. 求因子用sqrt(n)提高效率，防止超时