/*
题意:
1、找出连续的因子,最多的个数,然后因子大小要最小
输入:输入一个数字,最大是int的最大
输出:输出连续依着因子个数,然后因子连乘
2、解题:
1、N不会被除自己以外的大于根号N的整数整除,
2、因此只需要从2~根号N遍历连续整数的第一个,求此时N能被最多多少个连续整数的乘积整除
3、在此过程中,如果有发现长度比当前最长长度anslen更长的情况,就更新ansLen和对应的第一个整数anl
learn && worng:
1、需要用longlong ,而不是Int,防止相乘溢出
2、注意是这一点,从第一个因子开始,不断连续乘积,都可以被整除,因为都是因子,所以因子乘因子仍是因子的一部分
包括:
找到第一点
计算长度并更新
*/
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
int main(int argc, char** argv) {
LL n;
scanf("%lld",&n);
//sqrt为根号N,anslen为最长年连续整数,ansi为对应第一个整数
LL sqr = (LL)sqrt(1.0 * n),ansi = 0,anslen = 0;
for(LL i = 2;i<=sqr;i++){ //遍历连续的第一个整数
LL temp = 1,j = i; //temp为当前连续整数的乘积
while(1){ //让j从i开始不断+1,看最长能到多少
temp *= j; //获得当前连续整数的乘积
if( n % temp != 0) break; //如果不能整除n,那么结束计算
if(j - i + 1 > anslen){ //发现更长长度
ansi = i; //更新第一个整数
anslen = j - i + 1;//更新最长长度
}
j++; //j加1,下一个整数
}
}
if(anslen == 0){ //最大长度为0,说明根号N范围内没有解
printf("1\n%lld",n); //输出n本身
}else{
printf("%lld\n",anslen); //输出最大长度
for(LL i = 0;i < anslen;i++){
printf("%lld",ansi+i);
if(i< anslen - 1){
printf("*"); //!!!输出间隔的乘号
}
}
}
return 0;
}
网友评论