L1-006. 连续因子

时间限制 400 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 陈越

一个正整数N的因子中可能存在若干连续的数字。例如630可以分解为3*5*6*7，其中5、6、7就是3个连续的数字。给定任一正整数N，要求编写程序求出最长连续因子的个数，并输出最小的连续因子序列。

输入格式：

输入在一行中给出一个正整数N（1<N<2³¹）。

输出格式：

首先在第1行输出最长连续因子的个数；然后在第2行中按“因子1*因子2*……*因子k”的格式输出最小的连续因子序列，其中因子按递增顺序输出，1不算在内。

输入样例： 630 输出样例： 3 5*6*7

解题思路：用循环遍历找到最长连续因子的长度和第一个因子

#include<cstdio> #include<cmath> #include<cstring> #define LL long long using namespace std; int main() { LL n,a,b,x,y=-1,i,j; scanf("%lld",&n); LL m=(LL)sqrt(n); x=n; for(i=2; i<=m; i++) { if(n%i!=0) continue; a=1; for(j=i; j<=m; j++) { if(n%(a*j)!=0||a*j>n) break; a*=j; } if(j-i>y) {y=j-i; x=i;} } if(y==-1) y=1; printf("%lld\n",y); printf("%lld",x); for(LL t=x+1; t<y+x; t++) printf("*%lld",t); printf("\n"); return 0; }