PROBLEM LINK:
Author: Piyush Kumar
Tester: Kevin Atienza
Editorialist: Kevin Atienza
PREREQUISITES:
Combinatorics, Sperner’s theorem, Fermat’s little theorem
PROBLEM:
Given N in prime-factorized form p_1^{e_1}\cdot p_2^{e_2} \cdots p_M^{e_M}, an antichain is a set of divisors of N such that for every pair (x,y) of divisors, \text{rad}(x) doesn’t divide \text{rad}(y), and vice versa. What is the largest antichain, and how many largest antichains are there?
QUICK EXPLANATION:
The largest antichain size is {M \choose \lfloor M/2 \rfloor}.
Let P be the product of the exponents (e_i).
If M is even, then the number of largest antichains is P^{M-1 \choose M/2-1} \bmod 10^9 + 7. If M is odd, then the number of largest antichains is (P^{M-1 \choose \lfloor M/2 \rfloor -1} + P^{M-1 \choose \lceil M/2 \rceil -1}) \bmod 10^9 + 7.
P^{x \choose y} \bmod 10^9 + 7 can be done by reducing the exponent {x \choose y} modulo 10^9 + 6. Computing {x \choose y} modulo some m can be done by factorizing {x \choose y} using a sieve, and the formula \frac{x!}{(x-y)!y!}.
EXPLANATION:
Size of largest antichain
The number \text{rad}(n) is squarefree, which means each prime factor appears at most once in \text{rad}(n)'s prime factorization. We can think of a squarefree number as a set of primes (the set of its prime factors). For example, 1001 corresponds to the set of primes \{7, 11, 13\}, because 1001 = 7\times 11\times 13. In terms of sets, \text{rad}(x) divides \text{rad}(y) if and only if the set of primes of \text{rad}(x) is a subset of the set of primes of \text{rad}(y). Thus, we want to find the largest family of subsets of \{p_1,\ldots,p_M\} such that no subset contains any other subset.
But this is exactly what Sperner’s theorem answers! It says that the largest such family is of size {M \choose \lfloor M/2 \rfloor}, and a concrete example is the family of sets each of which contains \lfloor M/2 \rfloor distinct primes. It’s easy to see that each set in this family doesn’t contain any other, because they all have the same number of elements, and it’s also easy to see that there are {M \choose \lfloor M/2 \rfloor} such sets. In fact, the tricky part is in proving that this is indeed the largest family you can find. (A proof of this is given in the Wikipedia link above.) Thus, we now know the answer to the first question: {M \choose \lfloor M/2 \rfloor}.
Number of antichains
To get the second answer, let’s look at particular example. Let’s say M = 6 and N = 2^3 3^9 5^4 7^1 11^2 13^2. According to Sperner’s theorem, the largest such family of subsets of \{2,3,5,7,11,13\} is the following:
The question is now: how many ways can we choose divisors of N so that the family of their $\text{rad}$s are these numbers?
Let’s consider for example 30. How many divisors x of N = 2^3 3^9 5^4 7^1 11^2 13^2 have \text{rad}(x) = 30? We know which primes divide x, so we only need to select the exponents. In this case, we find that there are 3\times 9\times 4 x s whose \text{rad} is 30 (because the exponents of 2, 3 and 5 are 3, 9 and 4, respectively).
In general, for each prime p_i that appears in the \text{rad}, there are e_i choices for the exponent. We only need to multiply e_i across all primes in the \text{rad}, and then across all possible $\text{rad}$s. But how many sets does the prime p_i appear in? The answer is exactly {6-1 \choose 3-1}, because there are {6-1 \choose 3-1} ways to choose the 2 remaining members along with p_i. Thus, we need to multiply e_i a total of {6-1 \choose 3-1} times, so the answer in the above case is:
or simply
In general, the answer to the second question is simply the product of the $e_i$s, raised to the power {M \choose \lfloor M/2 \rfloor}!
But when M is odd, this is incomplete. This is because there are two largest families:
- The family of sets whose sizes are \lfloor M/2 \rfloor.
- The family of sets whose sizes are \lceil M/2 \rceil.
So, for odd M, the answer is the following:
where P is the product of the $e_i$s.
We now have an answer for the second question!
Computing P^{x \choose y} modulo 10^9 + 7
We need to compute a number of the form P^{x \choose y} modulo 10^9 + 7. Unfortunately, the exponent {x \choose y} is very large, and we can’t just reduce this number modulo 10^9 + 7 because that would be incorrect. (For example, 7^{11} \not\equiv 7^0 \equiv 1 \pmod{11}.) To make the exponent smaller, we need to use Fermat’s little theorem, which states that a^{p-1} \equiv 1 \pmod{p} for prime p and when a is not divisible by p. Since 10^9 + 7 is prime, this applies, and we can also infer that:
Thus, we can reduce {M-1 \choose \lfloor M/2 \rfloor-1} and {M-1 \choose \lceil M/2 \rceil-1} modulo 10^9+6, not 10^9+7.
Finally, how do we compute {x \choose y} modulo some number m, which is not necessarily a prime? One way is to simply compute the prime factorization of {x \choose y}. Since each prime factor of {x \choose y} is at most x, one can perform an Eratosthenes sieve up to x, and determine the exponents of the primes using the formula {x \choose y} = \frac{x!}{(x-y)!y!}. Finally, once you have the exponents one can then calculate {x \choose y} with modular exponentiation.
Time Complexity:
O(M \log \log M)