Marks on a lath
A joiner is marking a batten. First the batten is divided in half, with a pencil mark in the middle. Then into three equal parts, with two marks, then into four, and so on up to n equal parts. The ends of the batten are not marked, and if a new mark falls exactly on an old one, it is not drawn a second time: when dividing into four the middle is already marked, so there are only two new marks.
How many marks end up on the batten? The joiner has not yet decided how many parts the last division will be into, so compute the answer for several n.
Input
The first line holds the number of questions q (1 ≤ q ≤ 10⁵). Then q numbers n, one per line (1 ≤ n ≤ 10⁶).
Output
For each n, the number of distinct marks after dividing into 2, 3, …, n parts. For n = 1 the batten was not divided, and there are no marks.
Examples
Example 1
4 1 2 4 6
0 1 5 11
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
A mark made when dividing into b parts stands at the point a/b. When do two marks coincide? Write the fraction describing a mark so that each mark has exactly one form.
2Hint 2
Each mark is an irreducible fraction a/b with 0 < a < b ≤ n. How many such fractions have a given denominator b? That number has a name.
3The idea
A mark at the point a/b coincides with a mark from a smaller number of parts exactly when the fraction can be reduced. So a mark first appears when dividing into b parts, where b is the denominator of the irreducible fraction, and dividing into b parts adds as many new marks as there are numbers from 1 to b coprime to b. That is Euler’s function φ(b). The answer is φ(2) + φ(3) + … + φ(n). The values of φ for all numbers up to 10⁶ at once come from a sieve, and the answers to queries from prefix sums.
4Walkthrough
If b = p₁k₁ ⋯ prkr, then φ(b) = b · (1 − 1/p₁) ⋯ (1 − 1/pr). Hence the sieve: set phi[b] = b, and for each prime p go over its multiples, replacing phi[m] with phi[m] − phi[m] / p. The division here is always exact: by the time p is processed, phi[m] has accounted only for other prime divisors, and the factor p is still in it. In Python it is one line with a slice: phi[p::p] = [v - v // p for v in phi[p::p]].
The Go solution uses the linear sieve: φ(p · i) = φ(i) · p if p divides i, and φ(i) · (p − 1) otherwise. Each number gets its value once.
Then prefix sums total[n] = phi[2] + … + phi[n], and each query is one array access. For n = 10⁶ the answer is 303,963,552,391, which does not fit in 32 bits.
You can check yourself on a small case: for n = 4 the marks are 1/2, 1/3, 2/3, 1/4, 3/4, 5 in all = φ(2) + φ(3) + φ(4) = 1 + 2 + 2.
4+Solution
5Complexity
The sieve for φ is O(n log log n), or O(n) for the linear one, the prefix sums O(n), the queries O(1) each. Memory is O(n).
6Common mistakes
- Counting marks head-on. Adding b − 1 over all divisions counts coinciding marks many times: already on the first example you get 15 instead of 11.
- φ of each number by trial division. The formula is right, but it is about n√n operations, hundreds of millions for n = 10⁶.
- A GCD for every pair. Checking gcd(a, b) = 1 for all pairs is already quadratic, 5·10¹¹ pairs.
- Overflow. The sum up to 10⁶ is about 3·10¹¹.
Algorithms behind it
O(n log log n)
2 problems
NUM
Algorithm
Euclid's algorithm
The greatest common divisor of two numbers in O(log n) divisions with remainder.
O(log min(a, b))
2 problems
TEC
Technique
Prefix sums
The sum of any segment in O(1) after one pass; the two-dimensional version gives the sum of any rectangle of a picture.
O(n) to build, O(1) per query
2 problems