|Online Judge||Problem Set||Authors||Online Contests||User|
The Frobenius problem is an old problem in mathematics, named after the German mathematician G. Frobenius (1849–1917).
Let a1, a2, …, an be integers larger than 1, with greatest common divisor (gcd) 1. Then it is known that there are finitely many integers larger than or equal to 0, that cannot be expressed as a linear combination w1a1 + w2a2 + … + wnan using integer coefficients wi ≥ 0. The largest of such nonnegative integers is known as the Frobenius number of a1, a2, …, an (denoted by F(a1, a2, …, an)). So: F(a1, a2, …, an) is the largest nonnegative integer that cannot be expressed as a nonnegative integer linear combination of a1, a2, …, an.
For n = 2 there is a simple formula for F(a1, a2). However, for n ≥ 3 it is much more complicated. For n = 3 only for some special choices of a1, a2, a3 formulas exist. For n > 4 no formulas are known at all.
We will consider here the Frobenius problem for n = 4. In this case our version of the problem can be formulated as follows. Let four integers a, b, c and d be given, with a, b, c, d > 1 and gcd(a, b, c, d) = 1. We want to know two things.
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:
For every test case in the input file, the output should contain two lines.
3 8 5 9 7 5 8 5 5 1938 1939 1940 1937
6 11 14 27 600366 —1
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator