乐趣区

PAT A1096 质因子分解

这道题没有用常规的从小到大分解质因子,而是要连续的质因子;
其实思路很简单,从 2~sqrt(n) 进行枚举,使得 n%temp 是否能够取余为 0,temp 为连续质因子的乘积。在每次迭代中记录最长的质因子序列和相应的起始值;
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<vector>
#include<math.h>
using namespace std;
using std::vector;
typedef long long LL;
int main(){
LL n;
scanf(“%lld”,&n);
LL sqr=(LL)sqrt(1.0*n);
LL ansI=0,ansLen=0;
for(LL i=2;i<=sqr;i++){
LL temp=1,j=i;
while(1){
temp*=j;
if(n%temp!=0)
break;
if(j-i+1>ansLen){
ansI=i;
ansLen=j-i+1;
}
j++;
}
}
if(ansLen==0){
printf(“1\n%lld”,n);
}else{
printf(“%lld\n”,ansLen);
for(LL i=0;i<ansLen;i++){
printf(“%lld”,ansI+i);
if(i<ansLen-1){
printf(“*”);
}
}
}
system(“pause”);
return 0;
}

退出移动版