题目一个正整数 N 的因子中可能存在若干连续的数字。例如 630 可以分解为 3×5×6×7其中 5、6、7 就是 3 个连续的数字。给定任一正整数 N要求编写程序求出最长连续因子的个数并输出最小的连续因子序列。输入格式输入在一行中给出一个正整数 N1N2^31。输出格式首先在第 1 行输出最长连续因子的个数然后在第 2 行中按因子1*因子2*……*因子k的格式输出最小的连续因子序列其中因子按递增顺序输出1 不算在内。代码长度限制 16 KB时间限制 400 ms内存限制 64 MB栈限制 8192 KB思路解析根据题意求一串最长的连续因子使得这些因子的乘积能整除N并输出每个连续因子及其个数。由于要找的因子是相邻的整数我们只需求出最小的那个连续因子下图的因子1以及总的连续因子个数就能得到完整的最长连续因子。如果N是质数由于1不算连续因子只有它本身如果不是质数那么连续因子最大不会超过N^0.5。N最大取值2^31-1刚好是int的上限大约是2.14*10^9开根号后不超过1.5*10^5若要遍历整个区间求解一次循环内的运算次数不能超过10^3否则可能会超时。如果是暴力解法将2到N^0.5中的数分别当做最小连续因子求出对应的连续因子个数记录最长的连续因子个数及其最小因子。由于13的阶乘就超过了int的上限也就超过了N的最大取值所以每次求连续因子最多需要13次运算故两个循环嵌套后运算次数不超过2*10^6不会超时。直接使用暴力求解即可。最终作答这题需要的局部变量较多不要混淆了。#includeiostream using namespace std; int main(){ long long n; cinn; int start2;//连续因子起点即要求的最小因子 long long st2; int answer0;//最大连续因子数 while(st*stn){//由于n可能是int的上限st*st会超过int的取值范围要用long long int count0; int stempst; int kn; while(k%stemp0){//求连续因子个数和起点 k/stemp; count; stemp; } if(countanswer){//记录最小连续因子和总数 answercount; startst; } st; } if(answer0)//2到n^0.5没有任何因子说明n是质数 { cout1endl; coutnendl; return 0; } coutanswerendl; for(int istart;istartanswer-1;i){ couti; if(i!startanswer-1){ cout*; } } coutendl; return 0; }总结刚开始一直在想怎么优化算法反而离解题越来越远通过分析发现暴力求解的复杂度并不高。今后遇到难以优化算法的题目先算算暴力求解的复杂度。要点回顾int类型取值范围[-2^31 , 2^31-1] 即 [-2,147,483,648 , 2,147,483,648]2^31可以简记为214开头的十位数21亿4千万13! 2^31 12!竞赛中计算机一秒钟的运算次数一般是5*10^8不同的题目要求的运算时间可能不同但是只要把运算次数的数量级控制在10^8以内基本不会超时。由此可以得到处理各种数据量n时所需要的最大复杂度n10^8 - O(n)n10^6 - O(n*logn)n5*10^3 - O(n^2)n300 - O(n^3)O(2^n) - n25O(n!) - n11由于是刚开始发布算法题相关内容要点回顾会补充一些算法题基础知识之后只会针对题解回顾一些核心的内容。