[Quantity Water Problem]: There are three types that are equipped with A liters, B-liter, C-liter, A, B mutual, c> b> a> 0, now the C cartridge is filled with water, ask if it can be in the C cart Quantity D-water (C> D> 0). If you can, give the scenario.
answer:
The so-called modulus equation is the mode linear equation, such as an equation such as AX B (MOD C), where A, B, and C are constant, X is argument, this equation represents AX MOD C = B mod C, ie The AX and B die C are over. This amount of water problem is relatively convenient to use an analog mean, and the specific algorithm is analyzed.
The water process is actually inverting, there is always the following characteristics every time you fall. There is always no change in water in a cylinder; 2. Not a cylinder is filled with alcohol is another cartridge being fly; 3. The C barrel only plays a transfer, and the volume of the itself has no other limitation, which is not other than the water, and there is no other limit; so, suppose the A cartridge is filled with X times in the entire pouring process. The B cartridge is filled with Y, then: AX BY = D, (1) The X, Y is an integer, and may be an integer (representing the barrel (A or B) by the C-cylinder. The number of times), or the number of negative integers (indicating that the barrel (a or b) is filled, and then the number of times the C barrel is returned). Usually can be used to solve the equation (1), but this method is limited. We can convert the equation to: ax = -by d, further become AX ≡ D (MOD B), (20 This problem becomes the problem of solving the solution of the modulus equation (2). Solution X It is the total number of possible scenarios. The XI represents the number of times the A cylindries in the i-based scheme, and YI asked after the XI substituting equation (1) indicates the number of times the B cartridge is full.
For example, there are three type cylinders, A = 3, b = 7, c = 10, and all options for the amount of 5 liters of water in the C barrel. Solution: 3X ≡ 5 (MOD 7) Get x1 = 4, Y1 = -1 and X2 = -3, Y2 = 2, these two solutions corresponding to the down water scheme are as follows:
Solution 1: x1 = 4, y1 = -1
Number A b C Description 1 0 0 10 Initial state 2 3 0 7 From C to A, Pour the A fell 3 0 3 7 from A Pouring water to B, put a empty 4 3 3 4 from C Water to a, poured the A to the B, poured the a empty 6 3 6 1 from C to a, poured the A to the A, poured by the a fell 7 2 7 1 from A B, put B felt 8 2 0 8 from B poured into C, put B empty 9 0 2 8 from a pouring water to B, put a empty 10 3 2 5 from C to a , Put a fell 11 0 5 5 from a pouring water to B, empty a empty
In the whole process, a total of 4 times "from C dropping to a, put a fell", there is 1 time "Powder from B to C, put B empty"; program 2: X2 = -3, Y2 = 2
A number of times a b c Description 1 0 0 10 Initial state 2 0 7 3 Pouring from C to B, pouring B fell by 3 3 4 3 from B, pouring A Full 4 0 4 6 from A Water to C, put a empty 5 3 1 6 from B pouring water to a, pour the A fleet 6 0 1 9 from a pouring water to c, put a empty 7 1 0 9 from B pouring water to Amphink 8 1 7 2 from C to B, put the B felt 9 3 5 2 from B pouring water to a, pouring the A fell 10 0 5 5 from a pouring water to C , Empty a empty
During the whole process, a total of 3 times "Pumping it into C, putting a empty A", there is 2 times "from C dropping to B, put B full";
As for the method of solving analog equation, some books on the number theory have been introduced, and it is more troublesome, there are a lot of theorem formulas, I will give a program directly:
============================================================================================================================================================================================================= ======== C language program: ============================================= =====================
/ **********************************************************
Solving mode linear equation AX = B (mod n), n> 0 Copyright Starfish 2000/10/24
*************************************************** /
Void modular_linear_equation_solver (int A, int b, int N) {INT E, I, D; INT X, Y; D = EXT_EUCLID (A, N, X, Y); if (B% D> 0) {Printf (" No answer! / N ");} else {e = (x * (b / d))% N; for (i = 0; i / *************************************************** Expanding Ou Sili Germany for GCD (A, B) = AX by Copyright starfish 2000/10/24 *************************************************** / INT ext_euclid (int A, int b, int tent) {INT T, D; if (b == 0) {x = 1; y = 0; RETURN A;} D = EXT_EUCLID (B, A% B , X, Y); T = x; x = y; y = ta / b * y; Return D;} ============================================================================================================================================================================================================= ======== Pascal language program: ===================================== ===================== {=== Extended Euclide Rice, seeking GCD (A, B) and Meeting of the integer X and Y ===} Function Extended_euclid (A, B: Longint; VAR X, Y: longint): longint; var: longint; beginif b = 0 Then Begin Result: = a; x: = 1; y: = 0; endelse begin result: = extended_euclid (B, A Mod B, X, Y); T: = x; x: = y; y: = T- (a div b) * y; end; end;
