### PROBLEM LINK

### Panel Members

**Problem Setter:** Sergey Nagin

**Problem Tester:** Istvan Nagy

**Editorialist:** Sunny Aggarwal

**Contest Admin:** Praveen Dhinwa

**Russian Translator:** Sergey Nagin

**Mandarin Translator:** Hu Zecong

**Vietnamese Translator:** VNOI Team

**Language Verifier:** Rahul Arora

### DIFFICULTY:

Easy-Medium

### PREREQUISITES:

Mathematics, Sorting, Greedy.

### PROBLEM:

Given an integer A ( 0 <= A <= 10^{100} ) and N pairs of integers of the form (X, A/X) where X is an integer and A/X denotes the integer division of A by X.

It is also given that in no more than K such pairs the value of A/X is calculated incorrectly. Find the number of possible values of A modulo 10^9+7.

### QUICK EXPLANATION

For a given pair (X, A/X), if value of A/X is calculated correctly then the possible set of values that A can take according to this X can be represented

as a range from L to R where L = X * (A/X) and R = X * (A/X) + X - 1. We can represent all the given pairs as ranges (L, R) and as it given that in no

more than K such pairs the value of A/X is calculated incorrectly, answer will be the count of values that belongs to atleast N-K ranges.

### EXPLANATION

Let us represent i^{th} pair of integer as range L_i to R_i. Now, in order to calculate the number of integers that belongs to atleast N-K ranges, represent

a range as 2 separate pairs (L_i, 0) and (R_i, 1) where 0 denotes a marker for the starting of a range and 1 denotes a marker for ending of a range. Sort

all the 2*N pairs according to the first value.

Let us consider the following example to understand the solution better.

N = 3, K = 1

(X_1, A/X_1) = (30, 2)

(X_2, A/X_2) = (40, 2)

(X_3, A/X_3) = (50, 2)

Representing given pairs of integers as ranges:

(L_1, R_1) = (30 * 2, 30 * 2 + 30 - 1) = (60, 89) = (60, 0) and (89, 1) where 0 denotes starting marker and 1 denotes ending marker.

(L_2, R_2) = (40 * 2, 40 * 2 + 40 - 1) = (80, 119) = (80, 0) and (119, 1)

(L_3, R_3) = (50 * 2, 50 * 2 + 50 - 1) = (100, 149) = (100, 0) and (149, 1)

Sort the given ranges according to 1^{st} value.

(60, 0), (80, 0), (89, 1), (100, 0), (119, 1), (149, 1)

Now, maintain a counter to keep track for the number of ranges that an integer belongs to. Whenever a starting marker is encountered increment the counter variable by 1

and decrement it by 1 whenever an ending marker is encountered. Look at the below image to understand it better.

Now use this counter to calculate the count for the numbers that belongs to atleast N-K ranges. Look at the following fragment of code.

int mod = 1000000007; int counter = 0; // initialising counter to 0 int previous = 0; for(int i=0; i<2*N; i++) { if(A[i].second == 0) { counter ++; // incrementing counter on starting marker if( counter == N - K ) { previous = A[i].first; // value where we find our counter = N - K } } else { counter --; // decrementing counter on ending marker if( counter == N - K - 1 ) { // it means the value of counter upto this point // was at least N - K ans += A[i].first - previous + 1; ans %= mod; } } }

**NOTE:** If K = N then all the given values of A/X_i may be incorrect. In that case any value in the range \in [0, 10^{100}] can be a value for A. Therefore, the answer to

such case is (10^{100}+1) \% (10^9+7).

Please refer tester’s solution for better understanding of solution.

### COMPLEXITY

O(N\log(N))

### AUTHOR’S AND TESTER’S SOLUTIONS:

The author’s solution can be found here.

The tester’s solution can be found here.

The editorialist’s solution can be found here.