(PAT 1096) Consecutive Factors (质因子分解)

女爷i 2022-03-17 01:22 224阅读 0赞

Among all the factors of a positive integer N, there may exist several consecutive numbers. For example, 630 can be factored as 3×5×6×7, where 5, 6, and 7 are the three consecutive numbers. Now given any positive N, you are supposed to find the maximum number of consecutive factors, and list the smallest sequence of the consecutive factors.

### Input Specification: ###

Each input file contains one test case, which gives the integer N (1<N<231).

### Output Specification: ###

For each test case, print in the first line the maximum number of consecutive factors. Then in the second line, print the smallest sequence of the consecutive factors in the format `factor[1]*factor[2]*...*factor[k]`, where the factors are listed in increasing order, and 1 is NOT included.

### Sample Input: ###

630

### Sample Output: ###

3
    5*6*7

解题思路:

题目的意思是,给定一个数,找出最长的一串连续子串,使这串字串的积余输入的数为0

设输入的数为Num

我们从2---根号Num开始遍历,依次将Num与遍历到的数相余,如果取余为0,那么将Num/=j，如果这个数取余不为0,那么终止循环

每次终止循环后,保存当前连续字串的长度,依次比较,取最大者

#define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <algorithm>
    #include <math.h>
    #include <vector>
    using namespace std;
    long long num;
    
    int main() {
    	long long resLen = 0;
    	vector<long long> consecutives;
    	scanf("%lld", &num);
    	long long sqrtNum = (long long)sqrt(1.0*num);
    	for (long long i = 2; i <= sqrtNum; ++i) {
    		vector<long long> tempconsecutive;
    		long long tempLen;
    		long long tempNum = num;
    		long long j = i;
    		while (tempNum % j == 0) {
    			tempconsecutive.push_back(j);
    			tempNum /= j;
    			j++;
    		}
    		tempLen = j - i;
    		if (tempLen > resLen) {
    			resLen = tempLen;
    			consecutives = tempconsecutive;
    		}
    	}
    	if (resLen == 0) {
    		printf("1\n%lld", num);
    		return 0;
    	}
    	printf("%lld\n", resLen);
    	for (int i = 0; i < consecutives.size(); ++i) {
    		printf("%lld", consecutives[i]);
    		if (i < consecutives.size() - 1) printf("*");
    	}
    
    	system("PAUSE");
    	return 0;
    }