TwoClassTrip
SRM 847 · 2023-06-22 · by misof
Problem Statement
Time limit: 3 seconds.
Two non-empty classes of kids (class A and class B) went together on a school trip. During the trip they played a game. We know the following about the trip and the game:
- Class A contained at most N kids.
- Class B contained at most as many kids as class A.
- For the game, all kids in class A divided themselves evenly into teams of size a, and all kids in class B divided themselves evenly into teams of size b.
- The choice of a and b was a part of the game strategy. These two values could have been equal or distinct - each was chosen independently of each other.
- There is one additional limit on team sizes: each class can only choose a team size that can also be chosen by the other class.
For example, if N=100 one valid possibility is that class A had 100 kids who split into groups of 5, while class B had 70 kids who split into groups of 2.
(In the above scenario note that class B cannot pick team size 7: even though they can split evenly into teams of size 7, their opponents don't have this option and thus the last rule forbids this choice.)
Given N, count all scenarios consistent with the description given above, and return that count modulo 10^9 + 7.
Notes
- Formally, scenarios are 4-tuples (size of class A, size of class B, team size a, team size b).
Constraints
- N will be between 1 and 5,000,000, inclusive.
1 Returns: 1
Only a trivial solution: one kid in class A and one kid in class B, each forming a single team of size 1.
2 Returns: 6
Now we get five more options: if class A had size 2 and class B size 1 both classes had to form teams of size 1, and if both classes had two kids in them, there are four possible combinations of chosen team sizes.
3 Returns: 12
4 Returns: 27
5000000 Returns: 937336804
Submissions are judged against all 24 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TwoClassTrip with a public method int count(int N) · 24 test cases · 2 s / 256 MB per case