PTA团体程序设计天梯赛-练习集 做题笔记 L1-006 连续因子 (20 分)

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的因子或其本身。

二、如何维护保存我们求的最长最小因子串呢?
第一瞬间想到的或是最低级的方法当然是拿数组存。但仔细想想,我们求得的是一串连续的数字,同时也知道第一个数字的值和这一串数字的个数,即知道了起始地址与偏移量,于是我们只用维护当前最长最小因子的beginlength即可输出整个因子串。

三、需要注意的细节
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;
}
上一篇:PTA 天梯赛 L1-066 猫是液体 (5 分) 详解


下一篇:两数相加(链表形式)