天梯L1-006. 连续因子 (贪心+暴力)
程序员文章站
2022-06-10 19:02:02
...
思路:由于13!>2^31,所以最大长度不会超过12,那么我们就从长度为12开始搜索。之后就从2开始累乘,看是否满足条件。注意到因子中最大的不可能超过sqrt(n),所以可以做一些剪枝
注意点:素数!!
AC代码:
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int len,st,flag=0;
for(len=12;len>=1;len--)
{
int mid=sqrt(n);
for(st=2;st<=mid-len+1;st++)
{
int sum=1,i;
for(i=st;i<st+len;i++)
{
sum*=i;
if(n%sum!=0)
break;
}
if(i==st+len)
{
flag=1;
break;
}
}
if(flag==1)
break;
}
if(flag==1)
{
printf("%d\n",len);
printf("%d",st);
while(--len)
{
printf("*%d",++st);
}
}
else
{
printf("1\n");
printf("%d",n);
}
printf("\n");
return 0;
}