The Balanced Centrifuge Problem
Statement
Goal
(Inspired by https://www.youtube.com/watch?v=7DHE8RnsCQ8)Centrifuge is a piece of equipment that puts multiple test tubes in rotation at very high speeds. It consists of a cylindrical rotor with holes situated evenly along the circumference of the rotor.
Because the device is operating at high speeds, the center of mass of all tubes must coincide with the center of the rotor. We assume all tubes have the same mass.
For the sake of simplicity, we also assume that tubes are point masses, fixed firmly to the rotor. All at the same distance from the center. You may safely assume the (x,y) coordinates of tube
The problem is: Given a centrifuge with N holes and K tubes, is it possible to balance it?
example 1: given N =
example 2: given N =
example 3: given N =
Input
Line 1: An integer N for the capacity of the centrifuge.
Output
Line 1: An integer M for the number of different possible values of K.
Constraints
Example
Input
7
Output
1
Tags
Primes, Dynamic programming
Difficulty
Hard
Test cases
Prime Test
Input
7
Output
1
Validator 1 Validator
Input
13
Output
1
Small Composite Test
Input
6
Output
4
Validator 2 Validator
Input
8
Output
4
Medium Composite Test
Input
12
Output
10
Validator 3 Validator
Input
18
Output
16
Two Primes Test
Input
33
Output
13
Validator 4 Validator
Input
35
Output
11
Hard 1 Test
Input
2695
Output
2679
Validator 5 Validator
Input
1911
Output
1899
Hard 2 Test
Input
12345
Output
12337
Validator 6 Validator
Input
23457
Output
23445
Tricky Test
Input
136271
Output
135543
Validator 7 Validator
Input
169979
Output
169011
Power of a Prime Test
Input
131072
Output
65536
Validator 8 Validator
Input
177147
Output
59049
Solution language
Solution
Stub generator input