1096 Consecutive Factors (20 分)

题目传送门：1096 Consecutive Factors (20 分)

一、题目大意

给定一个数整数n，求n分解成多个因子相乘后，包含最长的连续因子的个数。
如果包含最长连续因为个数的解有多个，则输出最小的一组解。

二、解题思路

刚开始想歪了，我居然打表打出了12!内的连续整数成绩的种类和对应的数量，这样其实是错的，因为这个连续区间最多是【1，12】，然而，居然还能过5组数据，呵呵?只能说数据量太小了。

然后我就改了写法，就是直接实时判断，不预先打表。就是遍历n的每一个因子，然后判断以这个因为为连续序列的头一个数字，那么这个连续序列有多长。通过打擂台存储最长的连续序列即可。想要存储一个连续序列，只需要存第一个数字和序列的长度即可。

注意：此时遍历n的因子时，for的条件控制部分不能写成i*i<=n， 因为n过大时，i达到sqrt(n)+1的时候，i*i超过了int的范围，变成了负数，那i*i<=n依旧成立，造成死循环，结果就是在最后一组数据时运行超时。这里将i*i<=n改成i<=sqrt(n)即可。

三、AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin >> n;
	int max = 0, m = sqrt(n);// 注意此时m = sqrt(n)
	pair<int, int>res;
	for(int i = 2; i <= m; i++){// 如果此时写成i*i<=n，则最后一组数据无法通过，因为两个刚好大于sqrt(n)的值相乘超过了int范围，变成了负数，还能符合i*i<=n,造成了死循环，所以运行超时。
		if(n % i == 0){// i 为因子
			int a = n, b = i;// 从i开始，看连续的因子能有多长
			while(a % b == 0){
				a/=b;
				b++;
			}
			if(b - i > max){ // 是否能更新长度和结果
				max = b - i;
				res = {i, max};
			}
		}
	}
	if(!max){
		cout << 1 << endl << n << endl;
		return 0;
	}
	cout << max << endl;
	cout << res.first;
	for(int i = 1; i < res.second; i++){
		cout << "*" << res.first+i;
	}
	cout << endl;
}

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/100550483