There are an integer sequence A1,...,AN consisting of N terms, and N buttons. When the…
- User
There are an integer sequence A_1,...,A_N consisting of N terms, and N buttons. When the i-th (1 ≦ i ≦ N) button is pressed, the values of the i terms from the first through the i-th are all incremented by 1.
There is also another integer sequence B_1,...,B_N. Takahashi will push the buttons some number of times so that for every i, A_i will be a multiple of B_i.
Find the minimum number of times Takahashi will press the buttons.
Constraints
- All input values are integers.
- 1 ≦ N ≦ 10^5
- 0 ≦ A_i ≦ 10^9(1 ≦ i ≦ N)
- 1 ≦ B_i ≦ 10^9(1 ≦ i ≦ N)
Input
The input is given from Standard Input in the following format:
N A_1 B_1 : A_N B_N
Output
Print an integer representing the minimum number of times Takahashi will press the buttons.
Examples
Input
3 3 5 2 7 9 4
Output
7
Input
7 3 1 4 1 5 9 2 6 5 3 5 8 9 7
Output
22
Assistant
We need to find minimum total number of button presses. Buttons: for i=1..N, pressing button i increments A_1...A_i by 1 each. This is similar to operations that add 1 to a prefix of length i. We can press each button any number of times (non-negative integer). Starting from given A_i, we can apply operations to achieve that for each i, A_i' (final) is a multiple of B_i. We want minimize total presses sum over i of x_i where x_i is number of times we press button i.
Let x_i be nonnegative integer number of presses of button i. Then final value at position k is A_k + sum_{i=k..N} x_i? Wait careful: Button i increments positions 1..i. So after all operations, the increment added to position k is sum of x_i for all i such that i >= k (since those buttons include position k). More precisely: For a given position j, the total addition is sum_{i=j}^{N} x_i because any button with index i >= j affects position j (since its prefix covers up to i). So final value A'j = A_j + S_j, where S_j = sum{i=j}^{N} x_i.
Thus we have constraints: A'_j ≡ 0 mod B_j, i.e., A_j + S_j ≡ 0 (mod B_j). Or equivalently, S_j ≡ -A_j (mod B_j). Since S_j are suffix sums of x_i. Define x_i ≥ 0 integers.
We want minimize total sum T = sum_{i=1}^{N} x_i.
Observation: S_j are decreasing: S_1 = total sum of all x_i, S_2 = total sum minus x_1, ..., S_N = x_N.
Also S_j = S_{j+1} + x_j (since S_{j+1}= sum_{i=j+1}^{N} x_i). So we have recurrence: x_j = S_j - S_{j+1}, and x_j ≥ 0 implies S_j ≥ S_{j+1}.
Now constraints: for each j, S_j ≡ r_j (mod B_j), where r_j = (-A_j) mod B_j, i.e., the non-negative remainder needed: we need S_j ≡ (-A_j) mod B_j. Actually we need S_j mod B_j = (-A_j) mod B_j, i.e., S_j ≡ (B_j - (A_j mod B_j)) mod B_j? But careful: A_j + S_j ≡ 0 mod B_j => S_j ≡ -A_j (mod B_j). So we can define required residue d_j such that 0 ≤ d_j < B_j and d_j ≡ (-A_j) mod B_j. So d_j = (B_j - (A_j mod B_j)) mod B_j. If A_j % B_j == 0 then d_j = 0.
So we need to choose nonnegative integers S_1 ≥ S_2 ≥ ... ≥ S_N (since x_i >=0) with S_j ≡ d_j (mod B_j). Minimize S_1 (since total presses T = S_1, because S_1 = sum_{i=1}^N x_i). Yes total sum = S_1.
Thus our goal is to find the minimal possible S_1 (nonnegative integer) such that there exists a sequence S_1 ≥ S_2 ≥ ... ≥ S_N (all integers) and for each j, S_j ≡ d_j (mod B_j). And then the minimal total presses is that S_1.
We can treat this as constructing S_N up to S_1. Since S_1 must be as small as possible, we need to assign the smallest feasible values to S_j while preserving monotonic nonincreasing sequence and congruence conditions.
This looks like a typical greedy backward construction: Start from j = N down to 1, choose the smallest possible S_j that satisfies S_j ≡ d_j (mod B_j) and S_j ≤ S_{j+1}? Wait the constraint is S_j ≥ S_{j+1} (since sequence nonincreasing from S_1 to S_N). Actually S_j is sum from j to N, so as j decreases, we include more x_i, so S_j increases. So S_1 ≥ S_2 ≥ ... ≥ S_N. So when we go from N to 1, we have that S_j ≥ S_{j+1}. So for j=N, we need to choose S_N ≡ d_N mod B_N, minimal nonnegative. Then for j=N-1, we need S_{N-1} ≡ d_{N-1} mod B_{N-1}, and S_{N-1} ≥ S_N. To minimize overall S_1, we want each S_j as small as possible subject to these constraints. Since S_1 is the sum, and it is built from these lower bounds, we can propagate constraints forward.
But careful: The minimal S_1 may not be achieved by greedily choosing smallest possible each S_j? Let's think: We want minimize S_1. The variables are linked: S_1 ≥ S_2 ≥ ... ≥ S_N. The constraints are congruence constraints on each S_j. This is reminiscent of solving a system of congruences with monotonicity. Usually, the optimal is to set S_j to the smallest number that is ≥ S_{j+1} and ≡ d_j mod B_j. Because making S_j as small as possible does not harm later constraints (since S_{j-1} must be ≥ S_j). But is it always optimal to minimize each S_j locally (given the suffix constraints) to achieve minimal S_1? Since S_1 is the top, it depends on all lower ones. But if we minimize S_N, then for j=N-1, we minimize S_{N-1} subject to being congruent and at least S_N; then continue. Intuitively, if we increase some S_j beyond its minimal possible, it might allow a smaller S_{j-1}? Actually no: S_{j-1} must be ≥ S_j, so if we increase S_j, it might force S_{j-1} to be at least that larger value, potentially increasing S_{j-1} as well. Could increasing S_j allow S_{j-1} to be smaller? Let's see: Suppose we have constraints: S_{j-1} ≡ d_{j-1} mod B_{j-1} and S_{j-1} ≥ S_j. If S_j is minimal, it might be some value; S_{j-1} must be ≥ S_j. To minimize S_{j-1}, we would pick the smallest number that is ≥ S_j and congruent to d_{j-1} mod B_{j-1}. If we increase S_j, then the lower bound for S_{j-1} increases, so the minimal possible S_{j-1} becomes larger or at least not smaller. So increasing S_j cannot decrease S_{j-1}. Conversely, decreasing S_j (if possible) could allow lower S_{j-1}, but we already choose S_j minimal subject to its own congruence and its lower bound from S_{j+1}. However, it might be that by increasing S_j, we could adjust the congruence for S_{j-1} to be smaller? Wait S_{j-1} must be at least S_j. If S_j is minimal, we may have S_j = some value. Suppose the smallest number ≥ S_j that is ≡ d_{j-1} mod B_{j-1} is some value Q. If we increase S_j to a larger value R, the smallest number ≥ R that is ≡ d_{j-1} mod B_{j-1} might be less than Q? That seems impossible: as the lower bound increases, the minimal candidate cannot decrease; it could stay same if R ≤ Q? Actually if R > S_j, the minimal candidate must be at least R, so it must be ≥ R > S_j. So it's larger. So increasing S_j can only increase or keep same (if R still <= the same candidate, but if candidate > S_j, R might be less than candidate if R <= candidate? But if R > S_j, and candidate is the smallest congruent number >= S_j, then if R <= candidate, then the smallest congruent number ≥ R is still candidate (since candidate >= R). So if we increase S_j but keep it below candidate, the minimal S_{j-1} remains candidate. But if we increase S_j beyond candidate, then we need to go to the next congruent number > R, which is larger. So the minimal S_{j-1} would not decrease; it stays the same or increases. So local minimization should be optimal.
Thus we can compute S_N, then work backwards: for j from N down to 1? Wait we need S_1 as final answer, but we compute from N to 1: start with S_{N+1} = 0? Actually no lower bound for S_N is 0? Since S_N = x_N ≥ 0, and there is no lower bound from below. So S_N must be congruent to d_N mod B_N, and minimal such is simply d_N. But careful: Could S_N be negative? No, x_i are nonnegative, so S_N = x_N ≥ 0. So we set S_N = the smallest nonnegative integer ≡ d_N mod B_N, which is d_N (since 0 ≤ d_N < B_N). So S_N = d_N.
Now for j = N-1 down to 1: we have S_{j} must satisfy S_j ≡ d_j mod B_j and S_j ≥ S_{j+1}. We want to choose the smallest such S_j. This is: find the smallest integer >= S_{j+1} that is congruent to d_j modulo B_j. That's a classic step: compute r = (d_j - (S_{j+1} mod B_j)) mod B_j (i.e., the amount needed to add to S_{j+1} to reach a number ≡ d_j mod B_j). Then candidate = S_{j+1} + ((d_j - S_{j+1}) mod B_j). But careful with negative: The smallest number >= S_{j+1} that is ≡ d_j (mod B_j) is: if S_{j+1} mod B_j <= d_j, then candidate = S_{j+1} + (d_j - (S_{j+1} mod B_j)); else candidate = S_{j+1} + (B_j + d_j - (S_{j+1} mod B_j)). This can be expressed as: let rem = S_{j+1} % B_j; then need increment = (d_j - rem + B_j) % B_j; then S_j = S_{j+1} + increment.
Thus we can compute S_j sequentially. Finally S_1 is answer.
But is this always minimal total presses? Let's test with examples.
Example 1: N=3 A:3,2,9 B:5,7,4 Compute d_j: A1=3, B1=5 => A1 mod 5 =3, need S1 ≡ -3 ≡ 2 mod5? Actually -3 mod5 =2. So d1=2. A2=2,B2=7 => 2 mod7=2 => need S2 ≡ -2 mod7 ≡5 mod7 => d2=5. A3=9,B3=4 =>9 mod4=1 => need S3 ≡ -1 mod4 ≡3 mod4 => d3=3.
Now compute: S3 = d3 = 3. j=2: S3=3, B2=7, d2=5. rem=3%7=3, need inc = (5-3+7)%7= (2+7?) Actually (5-3)=2, positive so inc =2? (5-3+7)%7= (2)%7=2? Wait formula inc = (d_j - rem + B_j) % B_j. For d2=5, rem=3 => (5-3+7)%7 = (9)%7=2. So S2 = 3+2=5. Check: 5≥3, 5 mod7=5=d2 ok. j=1: S2=5, B1=5, d1=2. rem=5%5=0, inc = (2-0+5)%5 = (2)%5=2 => S1=5+2=7. Answer =7 matches.
Example2: N=7, input: 3 1 -> A1=3,B1=1 => d1 = (-3) mod1 =0. 4 1 -> d2=0. 5 9 -> A3=5,B3=9 => 5 mod9=5, need -5 mod9=4 => d3=4. 2 6 -> A4=2,B4=6 => 2 mod6=2 => need -2 mod6=4 => d4=4. 5 3 -> A5=5,B5=3 => 5 mod3=2 => need -2 mod3=1 => d5=1. 5 8 -> A6=5,B6=8 => 5 mod8=5 => need -5 mod8=3 => d6=3. 9 7 -> A7=9,B7=7 =>9 mod7=2 => need -2 mod7=5 => d7=5.
Now compute backwards: S7 = d7=5. j=6: S6 must be >=5, ≡3 mod8. rem=5%8=5, need inc = (3-5+8)%8 = (6)%8=6 => S6=5+6=11. Check 11 mod8=3 ok. j=5: S5 >=11, ≡1 mod3. rem=11%3=2, need inc = (1-2+3)%3 = (2)%3=2 => S5=13. 13 mod3=1 ok. j=4: S4 >=13, ≡4 mod6. rem=13%6=1, inc=(4-1+6)%6= (9)%6=3 => S4=16. 16 mod6=4 ok. j=3: S3 >=16, ≡4 mod9. rem=16%9=7, inc=(4-7+9)%9= (6)%9=6 => S3=22. 22 mod9=4 ok. j=2: S2 >=22, ≡0 mod1 (always true). Smallest >=22 that is ≡0 mod1 is 22 (since any integer). So S2=22. j=1: S1 >=22, ≡0 mod1 => S1=22. Answer=22 matches.
So the algorithm appears correct.
But wait: Are there any constraints on the ordering? The suffix sums approach seems correct. However, we must be careful: The x_i must be integers, but they are automatically derived from the differences S_i - S_{i+1}. These differences are nonnegative because we enforce S_i >= S_{i+1}. In our construction, we ensure S_i >= S_{i+1} because we set S_i to be >= S_{i+1}. So x_i = S_i - S_{i+1} >= 0. So valid.
Thus the answer is simply S_1 computed by starting from S_N = d_N and for i from N-1 down to 1 compute S_i = smallest number >= S_{i+1} with S_i ≡ d_i mod B_i.
But is there any case where S_N = d_N is not feasible? Since d_N is in [0, B_N-1], and S_N must be >= 0, so it's fine. However, consider that S_N is a suffix sum x_N, which can be any nonnegative integer. So d_N is minimal, and we can always achieve that. But could it be that picking S_N = d_N leads to contradiction later? Since we propagate constraints, as long as we can find S_i >= S_{i+1} satisfying modulo, there's no other constraints. But there might be a scenario where at some step the needed S_i becomes huge, but still finite, so always feasible because we can always add multiples of B_i to get larger numbers. So solution always exists? Not necessarily: Is there any situation where it's impossible? Let's check: The problem statement implies that Takahashi can push buttons some number of times to achieve condition. But is it always possible? Possibly not; maybe there is no set of nonnegative integer presses achieving all conditions. But does our method detect impossibility? If for some i, we compute S_i = S_{i+1} + inc, but inc is computed via modulo, always gives a number, so it's always feasible. But is there any hidden condition? Let's think about the system: For any given S_{i+1}, we can always find an S_i that satisfies S_i ≡ d_i mod B_i and S_i ≥ S_{i+1} because we can take the smallest such. Since the set of numbers congruent to d_i mod B_i is infinite, there is always some >= any lower bound. So a solution always exists? But wait: S_i must also be >= S_{i+1}, but we are constructing from right to left. However, we need to ensure that at the end, x_i = S_i - S_{i+1} are integers (which they are). But is there any additional constraint from the fact that x_i are counts? They can be any nonnegative integer, so no.
Thus it seems that for any sequences A_i, B_i, there is always a solution. But is that true? Let's test extreme: N=1, A1=0, B1=5: need A1+S1 multiple of 5 => S1 ≡ 0 mod5. Minimal S1=0, which is allowed (press button 1 zero times). Yes.
Another: N=2, A=[1,1], B=[2,2]: d1 =? A1=1 => need S1 ≡ -1 mod2 => d1=1. A2=1 => d2=1. Compute S2 = d2=1. Then S1 must be >=1 and ≡1 mod2. Smallest is 1. So S1=1, answer=1. Check: x1=S1-S2=0, x2=S2=1. Press button2 once: increments A1 and A2 by1 => A1 becomes 2 (multiple of2), A2 becomes 2 (multiple of2). Works. So always possible.
What about A1=1, B1=2, A2=0, B2=2: d1=1, d2=0. S2 =0. Then S1 must be >=0 and ≡1 mod2 => smallest is1 => S1=1. x1=1, x2=0: press button1 once: increments A1 and A2 by1 => A1=2 ok, A2=1 not multiple of2? Wait A2 initial 0, after press button1 once, A2 becomes1, not multiple of2. But we also have S2=0 meaning we didn't press button2. So condition for position2: A2 + S2 = 0 + 0 =0 which is multiple of2? Actually S2 = sum_{i=2}^{2} x_i = x2 =0, so final A2=0? Wait careful: For j=2, S2 = sum_{i=2}^{N} x_i = x2. So we set x2 = 0. So after operations, A2 unchanged =0, which is multiple of2. So it's okay. So solution works.
Thus always possible.
But wait: The button 1 increments both A1 and A2. In our solution we used x1=1, x2=0. So A2 becomes 1 not 0? Actually A2 is initial 0, button1 increments positions 1 and 2, so if we press button1 once, A2 becomes 1. But we said x2 = 0, so no press on button2. However, the final value for position2 is A2 + sum_{i=2}^{2} x_i = A2 + x2 = 0 + 0 = 0? That seems contradictory: Why is button1 not affecting position2? In our definition, S_j = sum_{i=j}^{N} x_i. For j=2, S2 = x2 + x3 + ... + x_N. But button1 has index 1, which is less than j? Actually for position j, the buttons that affect it are those with index i >= j? Let's re-express: When we press button i, it increments positions 1 through i. So for position j, the set of buttons that affect it are those with i >= j (since button i covers positions 1..i, so it covers j if i >= j). Indeed, for j=2, buttons with i=2,3,...,N affect it, but button 1 does NOT affect position2 because button 1 only covers position 1. So our earlier statement that S_j = sum_{i=j}^{N} x_i is correct. So button1 does NOT affect A2. So our earlier example: A2=0, x1=1 does not affect A2. So final A2 = 0 + 0 =0, okay. Good. So everything consistent.
Thus solution is straightforward.
Now we need to handle up to N=100k, B_i up to 1e9. The algorithm is O(N). However, we must compute d_i = (-A_i) mod B_i. But careful: A_i can be 0..1e9, B_i up to 1e9. So we compute d_i = (B_i - (A_i % B_i)) % B_i. For A_i % B_i = 0, d_i = 0.
Then compute S = d_N. Then iterate i from N-1 downto 1: let needed = (d_i - (S % B_i) + B_i) % B_i S = S + needed
Finally output S.
But is there any potential overflow? S can be large. In worst case, consider B_i all large, but we might add up to B_i - 1 each step. So maximum S could be sum of (B_i - 1) but not exactly because each step we add a remainder less than B_i. N=1e5, B_i up to 1e9, so worst-case S could be up to 1e5 * (1e9 - 1) ≈ 1e14, which fits in 64-bit (2^63 approx 9e18). So we can use 64-bit (long long in C++ or Python int). Python int is fine.
But wait: The needed increment might be 0 if S % B_i == d_i. So S grows but maybe not always by less than B_i. However, S might become huge if we need to increase to meet congruence because S might be large from previous steps. But each step adds at most B_i - 1. But after many steps S could be huge, but maximum bound is: at each step, S becomes the smallest number >= previous S that is ≡ d_i mod B_i. Since previous S could be up to something, the new S will be at most previous S + (B_i - 1). So total increase sum over steps of at most (B_i-1). So S_final ≤ sum_{i=1}^{N} (B_i - 1) + d_N (which ≤ B_N-1). Roughly ≤ sum B_i, which ≤ 1e5 * 1e9 = 1e14, as said.
But wait: Could it be larger due to the accumulation where each step pushes S up significantly because the previous S is already large and the modulo condition forces a jump? The jump is at most B_i - 1 relative to the previous S. So yes.
Thus answer fits 64-bit.
Now we should confirm the reasoning for correctness more formally.
We can view the problem as: minimize S_1 subject to S_i ≡ d_i (mod B_i) and S_i ≥ S_{i+1} for i=1..N, with S_{N+1}=0? Actually we also need S_{N+1} = 0? Let's think: For consistency, after N, there is no more terms. However, S_N is sum of x_i from i=N to N, which can be any nonnegative integer. There is no lower bound from below except nonnegativity. But we set S_N = d_N (minimal). This works because we don't have a constraint from S_{N+1}. However, could we possibly choose S_N larger to reduce S_1? As argued earlier, making S_N larger might increase subsequent S_i, so likely not. But let's test a small case: N=2, suppose d2 = 0, d1 = 1, B1=3, B2=2. Then our method: S2 = 0 (d2). Then S1: S2=0, rem=0%3=0, need inc = (1-0+3)%3 =1%3=1? Actually (1-0+3)%3 = 4%3 =1, so S1=1. So answer =1. But what if we choose S2 = 2 (the next number congruent to 0 mod2 and >0)? Then S1 must be >=2 and ≡1 mod3, smallest such is 4 (since 1 mod3: 1,4,7... next >=2 is 4). So S1=4, total bigger. So minimal is 1.
What about case where d2 is not minimal? Suppose B2 large, d2 = 1, B2=10. S2 minimal =1. If we increased S2 to 11 (next ≡1 mod10), then maybe S1 could be smaller? Let's test with some numbers: Suppose B1=3, d1=2. S2=1 => S1 must be >=1 and ≡2 mod3 => smallest is 2. Answer =2. If we set S2=11 => S1 must be >=11 and ≡2 mod3 => smallest is 14? Actually 11 mod3=2? 11%3=2, so 11 is ≡2 mod3, so S1 could be 11? But S1 must be >= S2, and S1 ≡ d1 mod B1 =2 mod3. If S2=11 and 11 ≡2 mod3, then smallest S1 = 11. Answer=11. So larger S2 leads to larger answer.
Thus minimal S_N is best.
Hence the greedy is optimal.
But is there any subtlety about the fact that S_i are suffix sums, and we also need that x_i = S_i - S_{i+1} must be integer (they are) and nonnegative (enforced by S_i >= S_{i+1}). So okay.
Thus the answer is computed as described.
But wait: We should also consider the possibility that d_i might be computed as negative? Use modulo properly.
Now implement: read N, then for i from 1..N read A_i, B_i.
Compute d_i = (B_i - (A_i % B_i)) % B_i. For B_i=1, A_i%1=0, d_i=0.
Then let S = d_N.
For i from N-1 down to 1: inc = (d_i - (S % B_i)) % B_i # In Python, this works because % returns non-negative S = S + inc
Print S.
Let's test with the examples above.
Edge cases: N=1, then answer = d_1.
But need to verify that S = d_N works always: S_N must be congruent to d_N mod B_N, and minimal nonnegative. But is there any requirement that S_N must also be >= 0? yes. d_N is between 0 and B_N-1 inclusive, so it's fine. However, could there be a scenario where S_N = d_N leads to some x_i negative? No.
Now confirm more formally: Could there be a better solution with S_N > d_N but leading to a smaller S_1? Suppose we increase S_N, then S_{N-1} might be smaller? Wait S_{N-1} must be >= S_N. If we increase S_N, it raises lower bound for S_{N-1}, so the minimal S_{N-1} becomes larger or same. Thus S_{N-1} doesn't get smaller. However, could it allow S_{N-1} to be exactly something that reduces S_{N-2}? No because S_{N-2} >= S_{N-1} as well. So any increase in later S's cannot reduce earlier S's, because earlier ones need to be at least the later ones. So local minimization of each S_i given the future ones yields global minimum of S_1. This is a typical dynamic programming with monotonicity.
Thus solution stands.
Now let's consider the possibility that B_i could be 0? But constraints say 1 ≤ B_i, so fine.
Now code.
We'll implement in Python:
def solve(): import sys input = sys.stdin.readline N = int(input()) A = [0]*N B = [0]*N d = [0]*N for i in range(N): a,b = map(int,input().split()) d[i] = (b - a % b) % b # Python's % yields 0..b-1 for positive b B[i] = b # store B for later
S = d[N-1] for i in range(N-2, -1, -1): inc = (d[i] - (S % B[i])) % B[i] S += inc print(S)But careful: When we compute inc = (d_i - (S % B_i)) % B_i, note that if S % B_i == d_i then inc = 0. If d_i - (S% B_i) negative, Python's % yields positive remainder.
Time complexity O(N). Memory O(N) for storing d and B, which is fine.
But is there any need to store all? We can compute on the fly from end? Since we need d_i and B_i in reverse order, we could read all into lists and then process backwards. With N up to 1e5, storing is fine.
But we need to be careful that the values might be large; but Python int handles.
Now check examples.
Let's test with custom:
N=1, A=5, B=5 => d1=0, S=0, output 0. Indeed A1=5 already multiple of5, no presses needed.
N=2, A=[0,0], B=[5,7] => d1=0, d2=0 => S2=0, then inc for i=1: (0 - 0) %5=0 => S1=0. Output 0.
N=2, A=[4,6], B=[5,7] => d1 = (5-4%5)%5 = (5-4)%5=1, d2 = (7-6)%7=1. S2=1. For i=1: S%5=1%5=1, inc = (1-1)%5=0 => S1=1. So total presses 1. Check: Press button2 once: A2 becomes 7 multiple of7, A1 becomes 5 multiple of5? Actually button2 increments positions 1 and 2. So A1=4+1=5 ok, A2=6+1=7 ok. So 1 press.
Another test: Suppose A1=4, B1=10, A2=3,B2=5. d1=(10-4)%10=6, d2=(5-3)%5=2. S2=2. S%10=2, inc=(6-2)%10=4 => S1=6. So answer 6. Check: x2=S2=2, x1=S1-S2=4. So press button1 4 times, button2 2 times. Total increments: A1 gets + from button1 (4) + from button2 (2) =6, so A1'=4+6=10 multiple of10. A2 gets from button2: +2 => 3+2=5 multiple of5. Works.
Thus correct.
But there is a nuance: The suffix sum S_j = sum_{i=j}^{N} x_i. We derived that A'_j = A_j + S_j. This is true because button i (i ≥ j) contributes 1 each time to position j. And button i with i < j does not affect position j. So correct.
Now, is there any hidden condition that the number of button presses can be huge but we need minimal.
All good.
Now, what about potential integer overflow in languages like C++? Use long long (64-bit). Since max sum B_i can be 1e14, less than 2^63-1 (~9e18). So safe.
Now, edge case: B_i = 1. Then d_i = 0 always. In our algorithm, inc = (0 - S%1) %1 = (0-0)%1=0, so S remains unchanged. So answer becomes S from the last index where B_i >1? Let's test: Suppose all B_i=1. Then all d_i=0. So start S_N=0, then each inc=0 => S=0. Output 0. Indeed any A_i are already multiples of1, so zero presses.
Now case where B_i vary: S may grow.
We should also consider the possibility of using Python's negative mod: (d - S% B) % B works because Python's % yields non-negative remainder.
Now, is there any scenario where S becomes very large and computing S % B_i becomes expensive? No.
Thus solution is trivial.
But wait: Let's double-check the derivation: S_j = sum_{i=j}^{N} x_i. For j=1, S_1 = sum_{i=1}^{N} x_i. Indeed.
Now, one more nuance: The button press definition: "When the i-th button is pressed, the values of the i terms from the first through the i-th are all incremented by 1." So button i increments positions 1..i. That's exactly what we used.
Now, could there be an alternative interpretation: that the i-th button increments the i terms from the first through the i-th? That is same.
Thus solution is correct.
Now, note: In the input, there are N lines, each with A_i and B_i. The constraints: 0 ≤ A_i ≤ 10^9, 1 ≤ B_i ≤ 10^9.
Now, the algorithm: O(N) time, O(N) memory.
But maybe we can do O(1) memory by reading and storing arrays, but it's fine.
But is there any possibility that we need to output a number modulo something? No.
Now, double-check the proof of optimality more rigorously.
We have an optimization problem:
Minimize S_1 subject to: S_i ≡ d_i (mod B_i) for i=1..N, S_i ≥ S_{i+1} for i=1..N-1, S_N ≥ 0 integer.
We claim the greedy algorithm yields the unique minimal solution. We can prove by induction: For k from N down to 1, define f_k = minimal possible value of S_k given that we will later determine S_{k-1},... Actually we want minimal S_1. But we can think: Let's define the feasible set for suffix starting at index i, given that S_{i} must be at least some lower bound L (coming from S_{i+1}). The minimal feasible S_i given L is the smallest integer ≥ L such that S_i ≡ d_i mod B_i. Therefore, if we start with L_{N+1} = 0 (or rather S_{N+1} = 0, but S_N has no lower bound from below except 0? Actually S_N ≥ 0, but we can treat lower bound as 0. However, we need S_N to be congruent to d_N. So minimal S_N = smallest integer ≥ 0 congruent to d_N = d_N. So L_N = d_N. Then for i=N-1, minimal S_{i} given that S_{i+1} is fixed at L_{i+1}? But note: We cannot arbitrarily set S_{i+1} to L_{i+1} without considering that it may be suboptimal for S_i? Actually we need to minimize S_1. Suppose we have a solution where we choose S_{i+1} > L_{i+1}. Could that reduce S_i? S_i must be ≥ S_{i+1}, so if we increase S_{i+1}, the minimal S_i (given the mod condition) will be at least that increased value, thus it cannot be lower than the minimal S_i we would have if S_{i+1}=L_{i+1}. However, could it be that the minimal S_i for S_{i+1}=L_{i+1} is actually larger than if S_{i+1} were larger? That seems contradictory. Consider we have two values for S_{i+1}: a and b, with a < b. Then the set of possible S_i values for each is: for a, we need some S_i ≥ a and ≡ d_i mod B_i; for b, S_i ≥ b and ≡ d_i mod B_i. The minimal such S_i for a is the smallest number ≥ a congruent to d_i. For b, it's the smallest number ≥ b. Since b > a, the smallest ≥ b is either equal to the smallest ≥ a if that smallest ≥ a is already ≥ b (i.e., if that number is >= b) or else it's a larger number. In no case can it be smaller. So minimal S_i is monotonic nondecreasing in S_{i+1}. So to minimize S_i, we want S_{i+1} as small as possible. Therefore, by induction, setting each S_{i+1} to its minimal feasible value (given subsequent choices) yields minimal possible S_i. Hence the greedy yields global optimum.
Thus correct.
Now, the solution is simple.
We should also consider the case where d_i is defined as above, but we might be able to compute directly without storing B_i? Since we need B_i in reverse, we need to store them.
Now, the problem is from AtCoder? Possibly "Buttons" or something. Usually such problems are solved with this suffix method.
Now, implement.
But wait: There is also a possibility that we could have misinterpreted the button indices: "the i-th button ... the i terms from the first through the i-th are all incremented by 1." That's same.
Now, test with random small N brute force to verify. Let's do mental small: N=2, all possible small A,B. Our formula seems plausible.
Now, let's try a case where B_i are not necessarily powers? It's fine.
Now, let's think if there is any scenario where our assumption S_N = d_N is not minimal because S_N can be any number >= d_N that satisfies its modulo, but maybe we could choose a larger S_N to make some S_i smaller? As argued, larger S_N forces larger S_{N-1} (or same), so S_1 cannot be smaller. But there is a nuance: What if we choose S_N larger, but then for some i < N, the smallest number >= S_{i+1} that satisfies modulo may actually be equal to S_{i+1} itself if S_{i+1} already satisfies the congruence? That would keep S_i = S_{i+1} (if S_{i+1} ≡ d_i mod B_i). Could that happen with a larger S_{i+1}? Possibly. But if we choose S_{i+1} smaller, maybe the smallest ≥ that does not satisfy congruence, requiring a jump. Could that jump make S_i larger than if we had chosen a larger S_{i+1} that already satisfied the congruence? Let's examine:
Suppose we have index i. Let L = S_{i+1}. The minimal S_i = f(L) = smallest number ≥ L with congruence mod B_i. f(L) is a nondecreasing function of L, and it is piecewise constant: For L in [kB_i + d_i, (k+1)B_i + d_i - 1], f(L) = kB_i + d_i if L ≤ kB_i + d_i? Actually if L <= that number, then f(L) = that number. If L > that number, then f(L) = next multiple offset.
Specifically, let m = the unique integer such that d_i ≤ d_i obviously. The numbers satisfying congruence are: d_i, d_i + B_i, d_i + 2B_i, ... So for a given L, f(L) = the smallest number in that arithmetic progression that is ≥ L. So f(L) = ceil((L - d_i)/B_i)B_i + d_i, with the convention that if L ≤ d_i, then ceil negative yields 0? Actually if L <= d_i, then f(L)=d_i. More precisely: f(L) = d_i + B_i * ceil(max(0, L - d_i) / B_i). This is monotonic nondecreasing, but not strictly: it may stay constant over an interval: For L in [d_i, d_i + B_i], f(L) = d_i if L <= d_i? Wait if L > d_i, say L = d_i + 1, then ceil((1)/B_i) = 1? Actually (L - d_i) = 1, ceil(1/B_i) = 1 for any B_i > 1? Actually ceil(1/B_i) = 1 if 1/B_i > 0? But ceil of a positive number less than 1 is 1. So f(L) = d_i + B_i * 1 = d_i + B_i. That's a jump. But if L = d_i, then f(L) = d_i. So the function is: f(L) = d_i if L ≤ d_i; else = d_i + B_i * ceil((L - d_i)/B_i). Since (L - d_i)/B_i is between 0 and something. For L just above d_i, ceil((L - d_i)/B_i) = 1 (since (L-d_i) >0 and < B_i, ceil gives 1). So f(L) jumps to d_i + B_i. So it's constant only for L ≤ d_i, then jumps. Actually it's not constant after d_i: for L in (d_i, d_i + B_i], ceil((L - d_i)/B_i) = 1, so f(L)=d_i + B_i constant on that whole interval. Then for L in (d_i+B_i, d_i+2B_i], f(L)=d_i+2B_i, etc. So f(L) is a step function: it is constant on intervals [d_i + kB_i, d_i + (k+1)*B_i]? Let's check: For L exactly d_i, f = d_i (k=0). For L in (d_i, d_i+B_i], f = d_i+B_i (k=1). So yes, f(L) = d_i + B_i * k, where k = 0 if L ≤ d_i, else k = ceil((L - d_i)/B_i). So for L ∈ (d_i + (k-1)B_i, d_i + k B_i] (with k>=1), f = d_i + k B_i. So as L increases, f(L) stays same over each interval of length B_i, then jumps at the next multiple.
Now, suppose we have S_{i+1} = L. If we increase L, f(L) may stay same if L remains within the same interval; thus S_i could be unchanged. But if L is originally smaller, maybe f(L) = some value; if we increase L slightly to the next interval start, f(L) might actually jump to a larger value. However, can increasing L cause f(L) to become smaller? No, because it's nondecreasing. Could increasing L cause f(L) to stay the same while other earlier S's become smaller? Not possible because earlier S's are determined by f on S_{i+1}. If we increase L but f(L) stays the same, then S_i unchanged. But then S_{i-1} depends on S_i. But could making L larger allow S_{i-1} to be smaller? Since S_{i-1} must be ≥ S_i, if S_i unchanged, then S_{i-1} is unchanged as well (since its lower bound is same). If S_i becomes larger (jump), then S_{i-1} lower bound increases. So never decrease S_{i-1}. So increasing S_{i+1} cannot reduce S_1.
Thus the greedy is optimal.
Now, we also need to ensure that we start with S_N as minimal (0 lower bound). Since S_N has no lower bound except >=0, the minimal is d_N. So done.
Now, confirm that the algorithm yields integer S.
Implementation details: Since we use Python, we need to be careful about large input reading. Use sys.stdin.buffer.
Now, just to be thorough, we'll test a few random cases with brute force for small N (like N<=5, small B) to validate. But here we trust reasoning.
Now, consider scenario where B_i is not coprime? Not relevant.
Thus answer is straightforward.
Now, I'll produce the final solution with explanation.
But the user asked: "There are an integer sequence A_1,...,A_N consisting of N terms, and N buttons. When the i-th (1 ≦ i ≦ N) button is pressed, the values of the i terms from the first through the i-th are all incremented by 1.
There is also another integer sequence B_1,...,B_N. Takahashi will push the buttons some number of times so that for every i, A_i will be a multiple of B_i.
Find the minimum number of times Takahashi will press the buttons."
We'll provide the answer: compute d_i, then compute suffix minimal.
Now, one more thought: Could there be an alternative approach using prefix differences? Another typical solution: Let y_i be the number of times button i is pressed. Then final A_i = A_i + sum_{j=i}^{N} y_j. We define z_i = sum_{j=i}^{N} y_j, so we need z_i ≡ -A_i (mod B_i) and z_i ≥ z_{i+1}. This is exactly our formulation.
Thus we are done.
Now, we will output the code.
But wait: In the input format, there is N then N lines each with A_i B_i. So code accordingly.
We need to ensure we handle large N efficiently.
Now, final code:
import sys
def solve(): import sys input = sys.stdin.readline N = int(input()) B = [0]*N d = [0]*N for i in range(N): a,b = map(int,input().split()) d[i] = (b - a % b) % b B[i] = b S = d[N-1] for i in range(N-2, -1, -1): inc = (d[i] - (S % B[i])) % B[i] S += inc print(S)
if name == "main": solve()
Now, we need to consider if there is any edge case: For B_i=1, d_i=0. S%1=0, inc=0, fine.
One more: If A_i is already multiple of B_i, then d_i=0. So we may get S unchanged if S% B_i == 0.
Now, consider if N=0? Not possible.
Thus answer.
Now, I'll produce final response with explanation and code. We can model the problem using suffix sums. Let (x_i) be the number of times button (i) is pressed ((x_i \ge 0)). After all operations, the value at position (j) becomes
[ A_j' = A_j + \sum_{i=j}^{N} x_i. ]
Define (S_j = \sum_{i=j}^{N} x_i). Then (S_1 \ge S_2 \ge \dots \ge S_N \ge 0) and the condition (A_j') is a multiple of (B_j) is equivalent to
[ A_j + S_j \equiv 0 \pmod{B_j} \quad\Longleftrightarrow\quad S_j \equiv d_j \pmod{B_j}, ]
where (d_j = (-A_j) \bmod B_j), i.e.
[ d_j = (B_j - (A_j \bmod B_j)) \bmod B_j. ]
We want to minimise the total number of presses (T = \sum_{i=1}^{N} x_i = S_1).
Thus the problem reduces to: find the smallest possible (S_1) such that there exist integers
(S_1 \ge S_2 \ge \dots \ge S_N \ge 0) and (S_j \equiv d_j \pmod{B_j}) for each (j).We construct the optimal (S_j) greedily from right to left.
- For (j = N): the smallest non‑negative integer satisfying the congruence is (S_N = d_N).
- For (j = N-1, N-2, \dots, 1): given (S_{j+1}), we need the smallest integer (S_j) such that
(S_j \ge S_{j+1}) and (S_j \equiv d_j \pmod{B_j}). This is
[ S_j = S_{j+1} + \big((d_j - (S_{j+1} \bmod B_j)) \bmod B_j\big). ]
The final answer is (S_1).
The algorithm runs in (O(N)) time and uses (O(N)) memory, well within the limits.
import sys def solve() -> None: input = sys.stdin.readline N = int(input()) B = [0] * N d = [0] * N for i in range(N): a, b = map(int, input().split()) d[i] = (b - a % b) % b # required residue mod b B[i] = b # start from the last position S = d[N - 1] # process backwards for i in range(N - 2, -1, -1): inc = (d[i] - (S % B[i])) % B[i] S += inc print(S) if __name__ == "__main__": solve()