By Lindsey L. (11th Grade)
https://usaco.org/index.php?page=viewproblem2&cpid=1376 12/21/25
Concepts: number theory
Solution:
We can use a set to store all distinct month lengths.
For the case where there are <= 3 distinct month lengths, any number k <= min month length / 4 will work because there will be at most 3 different values mod k and there will be at least 4 weeks per month. We can sum all values from 1 to minimum month length / 4. To do this quickly, we use the formula n*(n+1)/2 which finds the sum of numbers from 1 to n.
For the other cases, we notice that if two months are equal mod k, their difference must be divisible by k. Then, the only possible values of k are ones that are divisors of the difference between two months, because otherwise there would be at least 4 distinct values mod k.
We can find all pairwise differences between the first 4 months and calculate their factors. We only need to check 4 months because anything that has more than 3 values mod k for the first 4 will also have that for all the months.
To calculate all the factors, we can simply loop from 1 to sqrt(difference) and add it to a set if it divides the difference.
After finding all possible values of k, we need to check if they work for all months by counting the number of distinct values mod k over all n months. If there are more than 3 distinct values or if it is greater than min month length / 4, we don’t include it in the sum.
