PTA团体程序设计天梯赛-练习集 做题笔记
L1-006 连续因子 (20 分)
一个正整数 N 的因子中可能存在若干连续的数字。例如 630 可以分解为 3×5×6×7,其中 5、6、7 就是 3 个连续的数字。给定任一正整数 N,要求编写程序求出最长连续因子的个数,并输出最小的连续因子序列。
输入格式:
输入在一行中给出一个正整数 N(1<N<231)。
输出格式:
首先在第 1 行输出最长连续因子的个数;然后在第 2 行中按 因子1*因子2*……*因子k
的格式输出最小的连续因子序列,其中因子按递增顺序输出,1 不算在内。
输入样例:
630
输出样例:
3
5*6*7
以上是题面
题解
经典的枚举好题
从初学者的角度,本题的难点有:
一、题意理解。此题容易误解成以下情况:
先求出输入的正整数N的全部因子,例如1260
的因子有2 3 4 5 6 7 9 10 12 14 15 18 20 21 28 30 35 36…
,那么答案就是2*3*4*5*6*7
。然而2×3×4×5×6×7=5040>1260
,很显然是错误的。这是因为题意是将N分解为一串因子,这些因子相乘=N。要满足这个条件,其实也就是我们所求的连续因子的乘积也是N的因子或其本身。
二、如何维护保存我们求的最长最小因子串呢?
第一瞬间想到的或是最低级的方法当然是拿数组存。但仔细想想,我们求得的是一串连续的数字,同时也知道第一个数字的值和这一串数字的个数,即知道了起始地址与偏移量,于是我们只用维护当前最长最小因子的begin
和length
即可输出整个因子串。
三、需要注意的细节
1、首先是遇到质数的情况。由于我们不输出1因子(N=1除外),所以遇到质数便输出1 \n N即可;
2、为啥我上面一直要强调最长且最小的因子串呢?因为这看似不起眼的最小其实有点细节嗷,稍不注意这因子串他就不是最小了。具体的位置我会在AC代码中注释出来。
以下是AC代码
/*
* @Author: 句蒻勾
* @Date: 2022-01-10 15:42:50
* @Last Modified by: 句蒻勾
* @Last Modified time: 2022-01-10 15:42:50
* @Description: L1-006 连续因子 (20 分)
*/
#include<bits/stdc++.h>
using namespace std;
long long cnt;
long long max_count;
long long N;
long long start; //由于之前有个测试点没过我就全部开了longlong XD
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N;
for(int i = 2; i <= sqrt(N); i++){ //注意枚举到sqrt(N)就行了
int j = i;
long long temp = N;
cnt = 0;
while(temp % j == 0){
temp /= j;
j++;//这样就可以连续地求因子了
cnt++;
}
if(cnt > max_count){//如果用>=就不是最小因子串了,而是最大,不符合题意
max_count = cnt;
start = i;//维护最长
}
}
if(max_count == 0){//质数特判
cout << 1 << endl;
cout << N;
}
else{
cout << max_count << endl;
for(int i = 0; i < max_count; i++){
cout << start + i;
if(i != max_count - 1){
cout << "*";
}
}
}
return 0;
}