PTA甲级考试真题练习96——1096 Consecutive Factors
程序员文章站
2022-06-07 11:46:10
...
题目
思路
对于每个质因子(小于等于num)i,从i开始遍历直到乘积不能被整除,记录其中最大序列
坑点
注意不要忽略为质数的情况,应该就输出质数本身,否则最后两个测试点运行超时
代码
#include <iostream>
using namespace std;
int main()
{
int num;
int maxlen = 0;
int start, end;
cin >> num;
int sqrtn = sqrt((double)num);
for (int i = 2; i <= sqrtn; ++i) {
if (num % i != 0)
continue;
int j = i;
int k = j;
while (true) {
k *= j + 1;
if (num % k != 0) break;
j++;
}
if (j -i + 1 > maxlen) {
maxlen = j - i + 1;
start = i;
end = j;
}
}
if(maxlen == 0){
cout<<1<<endl;
cout<<num;
return 0;
}
cout << maxlen << endl;
cout << start;
for (int i = start+1; i <= end; ++i) {
cout << "*" << i;
}
return 0;
}
推荐阅读
-
PTA甲级考试真题练习111——1111 Online Map
-
PTA甲级考试真题练习22——1022 Digital Library
-
PTA甲级考试真题练习18——1018 Public Bike Management
-
PTA甲级考试真题练习20——1020 Tree Traversals
-
PTA甲级考试真题练习30——1030 Travel Plan
-
PTA甲级考试真题练习17——1017 Queueing at Bank
-
PTA甲级考试真题练习8——1008 Elevator
-
PTA甲级考试真题练习23——1023 Have Fun with Numbers
-
PTA甲级考试真题练习5——1005 Spell It Right
-
PTA甲级考试真题练习11——1011 World Cup Betting