CompositeSmash
SRM 517 · 2011-05-25 · by rng_58
SRM 517 · 2011-05-25 · by rng_58 · Math
Problem Statement
Problem Statement
Toastwoman wants to be a magical girl. As training, she wants to make a ball that contains an integer target.
Initially she has a ball that contains an integer N. She can smash a ball that contains a composite number (see notes for definition) and break it into two balls. Each new ball will also contain an integer. If she smashes a ball that contains a composite number x and it breaks into two balls that contain y and z, it satisfies y &ge 2, z &ge 2 and yz = x. For example, if she smashes a ball that contains 12, it breaks into 2 and 6 or 3 and 4. Toastwoman can control the ball she smashes, but she can't control the numbers in the two new balls when there are multiple pairs of (y, z) that satisfy the above conditions. She can apply the described ball smash operation arbitrary number of times, but she can't smash a ball that contains a non-composite number.
If she can always make a ball that contains target, return "Yes" (quotes for clarity). Otherwise, return "No" (quotes for clarity).
Initially she has a ball that contains an integer N. She can smash a ball that contains a composite number (see notes for definition) and break it into two balls. Each new ball will also contain an integer. If she smashes a ball that contains a composite number x and it breaks into two balls that contain y and z, it satisfies y &ge 2, z &ge 2 and yz = x. For example, if she smashes a ball that contains 12, it breaks into 2 and 6 or 3 and 4. Toastwoman can control the ball she smashes, but she can't control the numbers in the two new balls when there are multiple pairs of (y, z) that satisfy the above conditions. She can apply the described ball smash operation arbitrary number of times, but she can't smash a ball that contains a non-composite number.
If she can always make a ball that contains target, return "Yes" (quotes for clarity). Otherwise, return "No" (quotes for clarity).
Notes
- A positive integer x is called a composite number if it has at least one divisor other than 1 and x. For example, 4 and 6 are composite numbers, while 1 and 5 are not composite numbers.
Constraints
- N will be between 2 and 100,000, inclusive.
- target will be between 2 and 100,000, inclusive.
Examples
0)
517 47 Returns: "Yes"
If she smashes 517, it breaks into 11 and 47.
1)
8 4 Returns: "Yes"
If she smashes 8, it breaks into 2 and 4.
2)
12 6 Returns: "No"
If she smashes 12 and it breaks into 3 and 4, she can't make 6.
3)
5 8 Returns: "No"
4)
100000 100000 Returns: "Yes"
She already has target.
Submissions are judged against all 183 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CompositeSmash with a public method string thePossible(int N, int target) · 183 test cases · 2 s / 256 MB per case