Solved
Difficulty: D2C-D2D

思考题 inspired by Create Mod

Assembly Line

There is an assembly line consisting of n machines. The i-th machine on the line holds an infinitely long input queue and a processing time of t_i seconds.

The machines work as follows: It takes the first item in its input queue (if there are none, wait till an item comes), process it in t_i seconds. As soon as it finishes, the machine ejects the result to the tail of the input queue of the next machine in line. Then it repeats the process.

Now, two ingredients share this assembly line. Ingredient A comes at time t=a\cdot n,n\in N and B comes at time t=b\cdot n,n\in N. If at any moment, the ingredient/intermediate products of A and B comes at the same time, A queues first. Find the final rate of produced product A (products/second) and product B after the assembly line stabilizes.

Examples

a=3,b=7,t=[1,2,1]

Answer={7/25, 3/25}

Constraints

Subtask 1(50%): 1\leq a,b\leq 10^5

Subtask 2(100%): 1\leq a,b\leq 10^9

Solution

By XGN.

We will only consider when gcd(a,b)=1,a<b for simplicity.

The problem can be rephrased as:

In the interval [0,ab) , there is a dot at position X if X is a multiple of a or b. Assume the interval is divided into k non-overlapping subintervals of length l_1,l_2,...,l_k. Find: ans=x+\sum_{i=1}^k \max(l_i,x) where x=\max t_i.

The found ans is the length of the repeating interval. The real answer to our problem is b/ans and a/ans respectively.

Let's count the number of intervals c_d of length d in l. One could find that c_d=2 for 1\leq d<a. The answer is then obvious.