Betty the Cat 2
Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 1.0 seconds
Betty the cat has started going to the gym and is looking to grow her muscles. To help with her bulk, she has bought two types of creatinefilled cookie boxes: ones with A cookies per box, and ones with B cookies per box. Betty has an infinite number of these. When she opens a cookie box, she is morally obligated to eat all the cookies in the box.
Betty has a target cookie quota of K cookies a day. She wants to know: what is the closest amount she can get to her target cookie quota, and what is the minimum number of boxes she needs for this amount.
Note: If you're using a typesensitive language such as C, C++, C# or Java, you should use 64bit integer types to prevent integer overflow. 64bit integer types include long
long
for C or C++, and long
for C# or Java.
Input
The input will contain three spaceseparated integers A, B and K on a single line.
Output
Output two numbers separated by a space  the smallest possible absolute difference between target and actual cookies consumed, and the minimum number of cookie boxes required to achieve this.
Constraints
For all subtasks:
 1 \le A, B \le 1{,}000
 1 \le K \le 10^{18}
Subtasks
 Subtask 1 (+10%): A = 1 and K \le 100{,}000
 Subtask 2 (+25%): A = B and K \le 100{,}000
 Subtask 3 (+40%): K \le 100{,}000
 Subtask 4 (+25%): No further constraints.
Sample Explanation
 In Sample 1, if Betty eats two boxes of two cookies and two boxes of three cookies, she meets her quota of ten cookies exactly. So, she is zero cookies off her quota and can achieve this with four boxes of cookies. This is the minimum amount of boxes possible.
 In Sample 2, the best Betty can do is eat no cookies. This puts her three cookies off her quota of three.
 In Sample 3, the best Betty can do is eat three boxes of eight cookies, totaling 24 cookies. This puts her one cookie off her quota of 23 cookies.

Sample Input 1
2 3 10
Sample Output 1
0 4

Sample Input 2
19 6 3
Sample Output 2
3 0

Sample Input 3
8 8 23
Sample Output 3
1 3