Bitmask DP

Tutorial

Solution

Problems

Bitmask over Primes

Rough Idea

In some number theory problems, it helps to represent each number were represented by a bitmask of its prime divisors. For example, the set $\{6,10,15\}$ can be represented by $\{0b011,0b101,0b110\}$ (in binary), where the bits correspond to divisibility by $[2,3,5]$.

Then, here are some equivalent operations between masks and these integers:

• Bitwise AND is GCD
• Bitwise OR is LCM
• Iterating over bits is iterating over prime divisors
• Iterating over submasks is iterating over divisors

Choosing a set with GCD $1$ is equivalent to choosing a set of bitmasks that AND to $0$. For example, we can see that $\{6,10\}$ doesn't have GCD $1$ because $0b011\&0b101=0b001\ne 0$. On the other hand, $\{6,10,15\}$ has GCD $1$ because $0b011\&0b101\&0b110=0b000=0$.

Problems