PAT A1096 Consecutive Factors (20分)

前言

传送门

正文

参考题解

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
/* 题意： 求一个数n的所有因数中最长的连续序列，若有多种方案， 输出连续序列中第一个数最小的序列。 思路：遍历2~sqrt(n)，求n最多能被多少个连续整数的乘积整除，在此过程中 若出现更长的连续序列，则更新这个序列的一个数以及序列的长度 注意点： 素数相关的题最好都用 long long，避免溢出 */
typedef long long LL; 

int main(){
	LL n;
	cin>>n;
	int front=0,len=0;
	for(LL i=2,j=(int)sqrt(1.0*n);i<=j;i++){
		LL temp=1,r=i;//temp表示当前连续整数的乘积 
		while(1){
			temp*=r;
			if(n%temp!=0)break;//如果不能整除n，则结束
			if(r-i+1>len){//发现更长的序列 
				front=i;
				len=r-i+1; 
			}
			r++;//下一个数 
		}
	} 
	if(len==0){
		//说明sqrt(n)内没有解，输出n本身
		printf("1\n%lld",n); 
	} else{
		printf("%lld\n",len);
		printf("%lld",front);
		for(LL i=1;i<len;i++){
			printf("*%lld",front+i);
		}
	}
	return 0;
}