Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Frobenius
Description The Let w_{1}a_{1} + w_{2}a_{2} + … + w using integer coefficients _{n}a_{n}w ≥ 0. The largest of such nonnegative integers is known as the Frobenius number of _{i}a_{1}, a_{2}, …, a (denoted by _{n}F(a_{1}, a_{2}, …, a)). So: _{n}F(a_{1}, a_{2}, …, a) is the largest nonnegative integer that cannot be expressed as a nonnegative integer linear combination of _{n}a_{1}, a_{2}, …, a._{n}For We will consider here the Frobenius problem for - How many nonnegative integers less than or equal to 1,000,000 cannot be expressed as a nonnegative integer linear combination of the values
*a*,*b*,*c*and*d*? - Is the Frobenius number of
*a*,*b*,*c*and*d*less than or equal to 1,000,000 and if so, what is its value?
Input The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format: - One line, containing four integers
*a*,*b*,*c*,*d*(with 1 <*a*,*b*,*c*,*d*≤ 10, 000 and gcd(*a*,*b*,*c*,*d*) = 1), separated by single spaces.
Output For every test case in the input file, the output should contain two lines. - The first line contains the number of integers between 0 and 1,000,000 (boundaries included) that cannot be expressed as
*a*⋅*w*+*b*⋅*x*+*c*⋅*y*+*d*⋅*z*, where*w*,*x*,*y*,*z*are nonnegative (meaning ≥ 0) integers. - The second line contains the Frobenius number if this is less than or equal to 1,000,000 and otherwise −1, meaning that the Frobenius number of
*a*,*b*,*c*and*d*is larger than 1,000,000.
Sample Input 3 8 5 9 7 5 8 5 5 1938 1939 1940 1937 Sample Output 6 11 14 27 600366 —1 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator