De3b0o's MathModel Ideal Gift (Çözgüdiň düşündirişi)

Solution

We notice that b_i \cdot x - a_i = x - a_i \bmod x , so the condition b_i \cdot x - a_i \le c is the same as x - a_i \bmod x \le c , and since we want this condition to be true for all $i$ , so we only care about the maximum value of x - a_i \bmod x , thus we only care about minimum value of a_i \bmod x.

now answer for a single query is largest $x$ such that x - \min(a_i \bmod x) \le c.

We can see that $x$ cannot be bigger than \min(a_1,a_2,....,a_n) + c , and if \min(a_1,a_2,...,a_n) + c > \max(a_1,a_2,...,a_n) then answer is \min(a_1,a_2,...,a_n) + c.

Otherwise answer is \le \min(a_1,a_2,...,a_n)+c \le max(a_1,a_2,...,a_n).

(\text{mx} = \max(a_1,a_2,...,a_n))

So if we imagine that we have a magic way to find , for every $x$ from $1$ to $\text{mx}$ , \min(a_i \bmod x) , then we can answer queries easily (using binary search or offline).

Now for the magic way.

For some $x$ , \min(a_i \bmod x) is equal to \min(\text{nxt}(0) \bmod x , \text{nxt}(x) \bmod x , \text{nxt}(2x) \bmod x , \text{nxt}(3x) \bmod x , and so on ...) and is equal to \min(\text{nxt}(0) \bmod x , \text{nxt}(x) \bmod x , \min(a_i \bmod 2x) \bmod x , \min(a_i \bmod 3x) \bmod x , \min(a_i \bmod 4x) \bmod x , ... ).

Where $\text{nxt(y)}$ is the smallest a_i where a_i \ge y.

Why is this true?

Imagine we have two elements from the array between $x$ and $2x$, let's call them y_1<y_2.

And because y1<y2, so y_1 \bmod x<y_2 \bmod x.

So we only care about the first element in the range $[x,2x]$ , and the same for ranges [2x,3x] , [3x,4x] ... An easy solution is to first precalculate $\text{nxt(x)}$ for each $x$ from $0$ to $\text{mx}$, and then for each $x$ iterate over all its multiples.

It requires O(\text{mx}\log(\text{mx}) + \text{precalculate}), which is more than O(5 \times 10^9), so we need a faster way.

For the precalculate, we can just use a two pointers approach, so it's $O(\text{mx})$.

And to find \min(a_i \bmod x) for every $x$ (iterating over them from largest $x$ to smallest), we can see that instead of iterating over all multiples of $x$ , we can only iterate over p \cdot x where $p$ is a prime number.

Why is this enough?

Because suppose we want to find \min(a_i \bmod x), as we said earlier, it's \min(\text{nxt}(0) \bmod x , \text{nxt}(x) \bmod x , \min(a_i \bmod 2x) \bmod x , \min(a_i \bmod 3x) \bmod x , \min(a_i \bmod 4x) \bmod x , ... ), we can notice that \min(a_i \bmod 4x) is already computed in \min(a_i \bmod 2x) and the same for any non prime number $z$ , \min(a_i \bmod zx) is already computed in all its factors.

So \min(a_i \bmod x) = \min(\text{nxt}(0) \bmod x , \text{nxt}(x) \bmod x , \min(a_i \bmod 2x) \bmod x , \min(a_i \bmod 3x)\bmod x , \min(a_i \bmod 5x) \bmod x , ... ).

But is the complexity fast enough?

Well we can calculate the number of operations this method makes using a single loop , and find out it's $3e8$ operations approximately.

Approximate complexity is O(\text{mx}\log(\log(\text{mx}))) , we leave the proof up to you.

To find all prime numbers up to $\text{mx}$ , we can use sieve in O(\text{mx}\log(\log(\text{mx}))).

So total complexity is O(2\text{mx}\log(\log(\text{mx})) + q\log(\text{mx})) which is fast enough to pass.

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)
 
using namespace std;

const ll N = 5e7+9;

int n , q , a , mn=1e9 , mx;
bool vis[N];
vector<int> p;
bool s[N];
int ans[N];

int main()
{
    d3
    for(int i = 2 ; N>i*i ; i++)
    {
        if(s[i])
            continue;
        for(ll j = i*i ; N>j ; j+=i)
            s[j]=1;
    }
    for(int i = 2 ; N>i ; i++)
    {
        if(!s[i])
            p.pb(i);
    }
    cin >> n >> q;
    for(int i = 1 ; n>=i ; i++)
        cin >> a , vis[a]=1 , mn=min(mn,a) , mx=max(mx,a);
    int lst = -1;
    for(int j = mx ; j>0 ; j--)
    {
        if(vis[j])
            lst=j;
        ans[j]=lst%j;
    }
    for(int j = mx ; j>0 ; j--)
    {
        if(j>mn)
            ans[j]=min(ans[j],mn);
        for(auto it : p)
        {
            if(it*j>mx)
                break;
            ans[j]=min(ans[j],ans[it*j]);
        }
    }
    for(int j = 1 ; mx>=j ; j++)
        ans[j]=j-ans[j];
    for(int j = mx-1 ; j>0 ; j--)
        ans[j]=min(ans[j],ans[j+1]);
    while(q--)
    {
        ll c;
        cin >> c;
        if(mn+c>mx)
        {
            c+=mn;
            cout << c << "\n";
            continue;
        }
        int l = 1 , r = mx;
        int an;
        while(l<=r)
        {
            if(ans[mid]<=c)
                an=mid,l=mid+1;
            else
                r=mid-1;
        }
        cout << an << "\n";
    }
}