SRM 643

div1 250: The one with factorization

Factorize `2 <= N <= 10^18`, but half of the vector containing the sorted prime factors is given to you as the input. (The even-indexed ones) For example, 18 = 2*2*3, the prime factors vector is {2,2,3}, which means that the input will be 18, {2,3}, get it?

Factorization is supposed to be a hard problem. And for `N <= 10^18` it is, specially given the constraints, not so much the 2 seconds execution constraint, but the 256 MB memory constraint, the available time to code stuff and the lack of being able to save useful stuff in hard drive before running each test case... I mean, the *n*x* factor command can certainly factorize some large numbers, but you are supposed to do things the manual way here rather than reuse code..

So factorizing `N` is out of the question, maybe that's why it has to include some factors in the input. My first instinct was to think, well, just divide `N` by the known prime factors, the remaining value `n` shall be small enough to factorize, right? This is false. Just imagine `N` equal to 2 multiplied by a large prime number close to `10^18 / 2`. The large prime number would be a bit too large to do the `O(sqrt(N))` factorization by trial division algorithm we normally use.

Second idea was to do some ad hoc things. If there is only one prime factor provided, it means the number of prime factors is either 1 or 2, these are both easy cases to solve (result is either `{"primes"[0]}` or `{"primes"[0], N/"primes"[0]}` ). But this doesn't help. Cases in which the input has more than one factor can still lead to a rather large `n` after dividing: `999999999999999896 = 2 * 2 * 2 124999999999999987`.

So the solution is based in the following logic: The very last prime number in the factorization can be rather large `O(N)`, large, but if it is really so large, it will be the only such large number in the factorization. If this number is in an odd position, it will be ignored, and the resulting `N` after dividing by the known factors will be large because it includes this prime number. So the idea (which may not be 100% correct) is to just do trial division up to the `sqrt(2000000000)` and then, if there is still a number after dividing that much, what's left ought to be a prime number, right? I have no idea how good this is.

typedef long long int64;
#define long int64
struct TheKingsFactorization
{
    vector<long> getVector(long N, vector<long> primes)
    {
        long n = N;
        for (long p: primes) {
            n /= p;
        }
        //for (long p = 2; p * p <= 2000000000LL; p++) {
        for (long p = 2; p * p <= n; p++) {
            while (n % p == 0) {
                n /= p;
                primes.push_back(p);
            }
        }
        if (n > 1) {
            primes.push_back(n);
        }
        sort(primes.begin(), primes.end());
        
        return primes;
    }
};
#undef long

I suspect there will be many challenges in the challenge phase. I prepared up some cases, it's unlikely I'll get to use them, because Petr is in my room. Finished typing this as the coding phase ended. Let's see what happens.