X-Factor Chains (POJ 3421)

This turns out to be a hard question. The difficult exist in that not only the longest chain length but also how many ways of longest chains is required to be returned. This is a problem related to prime factors of a number.

Given the last number , how will get produce longest X-Factors? Obviouly if we divide it with a number but , we can always divide and separately to produce a longer chain, so in the longest chain we should always dividing with a prime factor of to produce and then . So we first find prime factors of and greedily pick the smallest ones such that . Then we start from the to try dividing in case can be perfectly divided by some of many times. We greedily divide the smallest prime factors so that is divided to as slow as possible. Then at last we can represent as

That is, start from , if one time we muliply with one of the items(if the same item can be multiplied many times, it is counted every time) to produce , we will produce a seqence of . So the longest X-Fractor chains has length .

If we change the order of in producing from , we will get different ways to produce X-Factor chains with the same length (which is longest). We have the total ways of ordering to be:

We divide with each as if two of the same prime factors exchanged places, it will produce the same X-Factor chains.

import java.io.*;
import java.util.*;

public class XFactorChains {
    private static int[] primes(int N) {
        if (N < 2) return new int[0];
        boolean[] isprime = new boolean[N];
        Arrays.fill(isprime, true);
        int count = 1;
        for (int i = 3; i < N; i += 2) {
            if (!isprime[i]) continue;
            for (int j = i; (i * (long)j) < N; j += 2) isprime[i * j] = false;
            count++;
        }
        int[] res = new int[count];
        int idx = 0;
        res[idx++] = 2;
        for (int i = 3; i < N; i += 2) if (isprime[i]) res[idx++] = i;
        return res;
    }

    private static void solve(int[] primeList, int n) {
        long a = 0;
        long b = 1;
        long c = 0;
        for (int p : primeList) {
            if (n % p != 0) continue;
            while (n % p == 0) {
                n /= p;
                a++;
                c++;
                b *= a;
            }
            while (c > 0) b /= c--;
            if (n == 1) break;
        }

        System.out.printf("%d %d\n", a, b);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] ps = primes(1 << 20);
        while (in.hasNextInt()) {
            solve(ps, in.nextInt());
        }
    }
}