1096 Consecutive Factors (20分) / 小细节
程序员文章站
2022-06-07 11:45:04
...
题目描述
解析
连续因子最大为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是质数要更敏感!