PAT甲题题解-1096. Consecutive Factors(20)-（枚举）

题意：一个正整数n可以分解成一系列因子的乘积，其中会存在连续的因子相乘，如630=3*5*6*7,5*6*7即为连续的因子。给定n，让你求最大的连续因子个数，并且输出其中最小的连续序列。

比如一个数可以分解2*3*4*6*7*8，最大的连续个数为3，因为存在两个，输出最小的那个即2*3*4。

首先，一个数如果是合数，那么它的因子必定不会超过sqrt(n)或者sqrt(n)+1。如果为质数，那么只可能为自己，因为题目说了不包括1。

我们先将2~sqrt(n)+1中为n的因子存到factor数组中，然后枚举以每个factor[i]开始的情况，看与后面的是否连续，每连续一个，都要判断乘积是否为n的约数，如果是并且大于目前最大的长度，即更新。连续中断，则从下一个factor[i+1]开始。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string.h>

#include <cmath>

using namespace std;

const int maxn=<<;

int n;

int cnt;

int factor[maxn];

/*

初始化n所有可能的因子

如果n不为质数，那么n最大的因子<=sqrt(n)+1

*/

void init(int n){

    cnt=;

    int k=sqrt(n+0.5);

    //这里要注意是k+1,比如20=4*5

    for(int i=;i<=k+;i++){

        if(n%i==){

            factor[cnt++]=i;

        }

    }

}

int main()

{

    //printf("%d\n",(1<<31)-1);

    scanf("%d",&n);

    init(n);

    int maximum=;

    int l,r,q;

    /*

    枚举以每个factor[i]开始的情况

    q为连续的个数

    */

    for(int i=;i<cnt;i++){

        q=;

        int sum=;

        while(factor[i+q]==factor[i]+q && sum*factor[i+q]<=n){

            sum*=factor[i+q];

            q++;

            if(n%sum== && q>maximum){

                l=i;

                r=i+q-;

                maximum=q;

            }

        }

    }

    if(cnt>){

        printf("%d\n",maximum);

        printf("%d",factor[l]);

        for(int i=l+;i<=r;i++)

            printf("*%d",factor[i]);

    }

    //若n为质数

    else{

        printf("1\n");

        printf("%d",n);

    }

    return ;

}

巴特西

PAT甲题题解-1096. Consecutive Factors(20)-（枚举）

最新文章

热门文章