First, observe that since each person only wants some sum of pieces that total to ~\frac{1}{n_j}~, there must be some way for Fax to cut the turkey into equal pieces and give some number of pieces to each person. Thus, the largest piece should be ~\frac{1}{\text{lcm}(n_1,n_2,\dots,n_N)}~, where ~\text{lcm}()~ denotes the least common multiple function. For 40% of the points, we calculate the LCM and check if it can be made from the cuts. We can do this by seeing if the LCM can be divided by the distinct prime factors of the cuts. It is sufficient to use the distinct prime factors since cuts will be multiples of those distinct primes. It might not be possible to form the LCM exactly, but it is guaranteed that we will form some multiple of the LCM (for example, LCM = 3, and the only cut is 27).

Since calculating the LCM of 1000 numbers that are up to ~10^6~ will likely overflow any data-type (and time out otherwise due to the large number of digits), we need to make one more observation. We note that in order to form ~\text{lcm}(n_1,n_2,\dots,n_N)~, all distinct prime factors in all ~n_j~ must be present in the LCM. Since a cut can be repeated many times, all we need to check is if the distinct prime factors in all ~n_j~ are present in the set of distinct prime factors of the cuts.

In order to quickly generate primes, we can use the sieve of Eratosthenes in order to quickly generate primes, which has a time complexity of ~\mathcal{O}(N \log \log N)~, where ~N~ is the largest number to check.

Time Complexity: ~\mathcal{O}(K \log \log K + \pi(\sqrt{K}) \times (N+C))~, where ~K~ is the maximum of all ~c_i~ and ~n_j~ and ~\pi(x)~ denotes the pi function, which counts the number of primes less than or equal to ~x~.