FoxAndCake2 | Topcoder Archive

Problem Statement

Fox Ciel has c cherries and s strawberries. She wants to bake some cakes. While doing so, she wants to follow some rules:

She must use exactly all cherries and all strawberries she has.
The number of cakes can be arbitrary (i.e., any positive integer).
Different cakes may contain different amounts of cherries and strawberries.
Each cake must contain at least one cherry and at least one strawberry.
A cake will taste bad if the number of cherries and the number of strawberries it contains happen to be coprime. Therefore, the numbers of cherries and strawberries in a cake must never be coprime. (Two positive integers are coprime if their greatest common divisor is 1.)

You are given the ints c and s. Return "Possible" if Ciel can bake cakes according to the above rules, or "Impossible" if she cannot do so.

Definition

Class:: FoxAndCake2
Method:: isPossible
Parameters:: int, int
Returns:: String
Method signature:: String isPossible(int c, int s)
(be sure your method is public)

Constraints

c will be between 1 and 1,000,000,000, inclusive.
s will be between 1 and 1,000,000,000, inclusive.

Examples

```
74
```
```
109
```
```
Returns: "Possible"
```
One possible solution is to bake 3 cakes as follows: A cake with 21 cherries and 14 strawberries. A cake with 20 cherries and 40 strawberries. A cake with 33 cherries and 55 strawberries.
```
1000000000
```
```
1000000000
```
```
Returns: "Possible"
```
Here Ciel can simply make one huge cake with 1000000000 cherries and 1000000000 strawberries.
```
1
```
```
58
```
```
Returns: "Impossible"
```
Ciel only has 1 cherry, so the only option is to bake one cake with 1 cherry and 58 strawberries. However, 1 and 58 are coprime, so this is not a good cake.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.