欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

1096 Consecutive Factors (20分) / 小细节

程序员文章站 2022-06-07 11:45:04
...

题目描述

1096 Consecutive Factors (20分) / 小细节

解析

连续因子最大为sqrt(num)+1,并不是sqrt(num),因为如果num不是平方数,那么sqrt(num)向上取整和向下取整的两个整数可能恰好是连续因子,比如20=4*5
第一层循环从小到大扫描num的因子,第二层循环构造连除(或者连乘)。
只不过这里我遇到了一个坑…@aaa@qq.com,以下是遇坑代码:

#include <iostream>
#include <cmath>
using namespace std;
int num, temp;
int main() {
	cin >> num;
	int first = 0, len = 0, maxn = sqrt(num) + 1;
	for (int i = 2; i <= maxn; i++) {
		int j;
		temp = num;
		for (j = i; j <= maxn && temp%j == 0; j++) {
			temp /= j;
		}
		if (j - i > len) {
			len = j - i;
			first = i;
		}
	}
	if (first == 0) {
		len = 1; first = num;
	}
	cout << len << endl;
	for (int i = first; i < first + len; i++) {
		if (i != first) cout << '*';
		cout << i;
	}
	return 0;
}

这个坑一开始怎么也想不到…直到我把代码改成:

if (first == 0) {
		cout << 1 << endl << num;
		return 0;
	}
	cout << len << endl;
	for (int i = first; i < first + len; i++) {
		if (i != first) cout << '*';
		cout << i;
	}

最后一个测试点就通过了。我顿悟了…int型的最大值INT_MAX=2147483647刚好是一个质数,最后一个测试点应该就是它了。此时,first=2147483647,那么,first+len溢出了…其值为0,那么无法进入循环…太坑了…

以后一定要对溢出和INT_MAX是质数要更敏感!

相关标签: PAT 算法