题目粗心:
给出一个正整数 N, 求一段间断的整数,使得 N 能被这段间断整数的乘积整除。如果有多个计划,输入间断整数个数最多的计划; 如果还有多种计划,输入其中第一个数最小的计划。
算法思路:
刚开始审题不当认为是质因子合成,导致节约了很多工夫,该题的想法也比拟直观,咱们遍历从 2 到 N 之间的每一个数字,用 consecutiveMulti
保留每一个能够被 N 整除的间断序列的乘积,并且应用 len
保留最长的序列长度,begin
保留最长的序列的起始数字,让 consecutiveMulti
一直累乘直到不能被 N 整除地位(就相似于从 2 开始始终乘以 3,4,5,6… 直到 N 不能整除该间断乘积为止,而后再接着从 3 开始始终乘以 4,5,6,7,8… 以此类推),而后更新长度 len
和起始地位 begin
,这里得留神 i 的含意是每一个间断序列的起始地位,咱们这里应用nextNum
保留以后序列的下一个待乘的数字,初始为 i,而后在循环中,consecutiveMulti
会乘以 nextNum
, 并且其长度能够应用nextNum-i+1
来代替,因为在数字 i
和nextNum
之间的数字都是间断的,每次更新 nextNum
加一即可。其实在这里不必遍历 2 到 N,只用遍历到根号 N 即可,因为,第一,不存在 2 个因子都大于更号 N。第二,N 如果存在大于根号 N 的因子肯定无奈和后面的因子组成间断序列。第三,如果在 2 到根号 N 中没有 N 的因子, 那么在根号 N 和 N 之间也必然不会有 N 的因子,N 的因子只有 1 和 N 自身,然而题目因为对于 1 不思考,所以在 2 和根号 N 之间没有解的时候只有长度为 1 的间断序列 N。
提交后果:
AC 代码:
#include <cstdio>
#include <cmath>
using namespace std;
int main(){
int N;
scanf("%d",&N);
int sqrt_N = (int)sqrt(N * 1.0);
int begin = 0;
int len = 0;
for (int i = 2; i <=sqrt_N ; ++i) {
int consecutiveMulti = 1;// 从数字 i 开始的局部间断乘积
int nextNum = i;// 以后序列前面待乘的一个数字
while (true){
consecutiveMulti *= nextNum;
if(N%consecutiveMulti!=0) break;// 无奈整除以后序列退出循环
// 能够整除,更新长度
if(len<nextNum-i+1){
len = nextNum-i+1;
begin = i;
}
++nextNum;// 更新下一个待乘的数字
}
}
if(len==0){// 阐明不存在 2 到根号 N 的数字局部乘积能够整除 N,也即是以后的 N 只有一个因子(它本人)。printf("1\n%d",N);
}else {printf("%d\n",len);
for (int i = begin; i < begin+len; ++i) {printf("%d",i);
if(i<begin+len-1) printf("*");
}
}
return 0;
}