TheKingsFactorization

SRM 643 · 2014-08-25 · by Witaliy

SRM 643 · 2014-08-25 · by Witaliy · Brute Force, Greedy, Math

Show categories

Class Name: TheKingsFactorization

Return Type: long[]

Method Name: getVector

Arg Types: (long long, vector<long long>)

Problem Statement

The King of Byteland likes integer factorization. Your task is to help him factor the number N. You will be given the long N and you should return a long[] containing all prime factors of N sorted in non-decreasing order. Note that some primes may occur multiple times in the prime factorization of N. For example, for N = 60 the only correct return value is {2, 2, 3, 5} because 2*2*3*5 = 60.

To make this task easier, the King has decided to give you a hint. He already knows the correct factorization and he will tell you every second number in the correct return value. More precisely, in addition to N you will be given a long[] primes. The number of elements in primes will be (M+1)/2, rounded down, where M is the number of elements in the correct return value. For each valid i, primes[i] will be equal to the element 2i of the correct return value. (All indices are 0-based.)

Given N and primes, return the long[] containing the factorization of N.

Constraints

N will be between 2 and 1,000,000,000,000,000,000 (10^18), inclusive.
primes will contain the correct prime factors (as defined in the problem statement).

Examples

12
{2, 3}
Returns: {2, 2, 3 }

7
{7}
Returns: {7 }

1764
{2, 3, 7}
Returns: {2, 2, 3, 3, 7, 7 }

49
{7}
Returns: {7, 7 }

210
{2, 5}
Returns: {2, 3, 5, 7 }

Submissions are judged against all 208 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TheKingsFactorization with a public method vector<long long> getVector(long long N, vector<long long> primes) · 208 test cases · 2 s / 256 MB per case