Not Frequent
0/13

Authors: Michael Cao, Siyong Huang, Andrew Wang

### Prerequisites

DP problems that require iterating over subsets.

### Pro Tip

You can often use this to solve subtasks.

Focus Problem – read through this problem before continuing!

## Tutorial

Resources
CPHElevator Rides, SOS, Hamiltonian
PAPSexample - similar to Hamiltonian
CFHamiltonian walks
HE

Solution

## Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
ACEasy
Show Tags

Check AC
CFEasy
Show Tags

Check CF
Old GoldEasy
Show Tags

External Sol
Old GoldEasy
Show Tags

External Sol
CSESNormal
Show Tags

CPH 10.5
IZhONormal
Show Tags

YSNormal
Show Tags

View Solution
KattisNormal
Show Tags

View Solution

### 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 can be represented by (in binary), where the bits correspond to divisibility by .

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 is equivalent to choosing a set of bitmasks that AND to . For example, we can see that doesn't have GCD because . On the other hand, has GCD because .

### This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

Maybe this is just standard NT, but I've always thought about it as a bitmask. Also, any tutorials or more problems of this type?

### Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
CFHard
Show Tags

DP, Combinatorics

Check CF
CFVery Hard
Show Tags

Check CF
CFInsane
Show Tags

Check CF
CFInsane
Show Tags