作者:指针不指南吗
专栏:算法刷题🐾或许会很慢,但是不可以停下来🐾
文章目录
- 题目
- 题解
- 题意
- 步骤
- 总结
题目
题目链接
题解
题意
求解n的最长连续因子
和因子再相乘的积无关,真给绕进去了
步骤
双重循环,外层表示起点,内层用来寻找连续因子的最大长度
内层循环:temp=n 不断除以j++
代码从输入的整数 n 中寻找最长的连续因子序列。通过遍历从 2 到 n \sqrt{n} 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=0
int 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;
}
总结
真烧脑,断断续续做了一天
刚开始题目就理解错了,就开始写题
- 连续因子的求解get到了
for(int j=i;temp%j==0&&temp!=0;j++){ //求连续因数
temp/=j;
cnt++;
}
- cnt初始化是0
- 求因子用sqrt(n)提高效率,防止超时