El regalo ideal de MathModel de Deebo#11857

El regalo ideal de MathModel de Deebo (Editorial)

Autor del problema:	(De3b0o)
Preparado por:	Hasan Saleh (MathModel)
Editado por:	(De3b0o)

Solución

Notamos que $b_{i} \cdot x - a_{i} = x - a_{i} mod x$ b_i \cdot x - a_i = x - a_i \bmod x , así que la condición $b_{i} \cdot x - a_{i} \leq c$ b_i \cdot x - a_i \le c es la misma que $x - a_{i} mod x \leq c$ x - a_i \bmod x \le c , y dado que queremos que esta condición sea verdadera para todos $i$ , solo nos importa el valor máximo de $x - a_{i} mod x$ x - a_i \bmod x , por lo que solo nos importa el valor mínimo de $a_{i} mod x$ a_i \bmod x.

Ahora, la respuesta para una única consulta es el mayor $x$ tal que $x - min (a_{i} mod x) \leq c$ x - \min(a_i \bmod x) \le c.

Podemos ver que $x$ no puede ser mayor que $min (a_{1}, a_{2}, ...., a_{n}) + c$ \min(a_1,a_2,....,a_n) + c , y si $min (a_{1}, a_{2}, ..., a_{n}) + c > max (a_{1}, a_{2}, ..., a_{n})$ \min(a_1,a_2,...,a_n) + c > \max(a_1,a_2,...,a_n) entonces la respuesta es $min (a_{1}, a_{2}, ..., a_{n}) + c$ \min(a_1,a_2,...,a_n) + c.

De lo contrario, la respuesta es $\leq min (a_{1}, a_{2}, ..., a_{n}) + c \leq max (a_{1}, a_{2}, ..., a_{n})$ \le \min(a_1,a_2,...,a_n)+c \le \max(a_1,a_2,...,a_n).

( $mx = max (a_{1}, a_{2}, ..., a_{n})$ \text{mx} = \max(a_1,a_2,...,a_n))

Así que si imaginamos que tenemos una forma mágica de encontrar, para cada $x$ de $1$ a $mx$ , $min (a_{i} mod x)$ \min(a_i \bmod x) , entonces podemos responder consultas fácilmente (usando búsqueda binaria o fuera de línea).

Ahora para la forma mágica.

Para algún $x$ , $min (a_{i} mod x)$ \min(a_i \bmod x) es igual a $min (nxt (0), nxt (x) mod x$ \min(\text{nxt}(0) , \text{nxt}(x) \bmod x , $nxt (2 x) mod x$ \text{nxt}(2x) \bmod x , $nxt (3 x) mod x$ \text{nxt}(3x) \bmod x , y así sucesivamente...)

Donde $nxt(y)$ es el menor $a_{i}$ a_i donde $a_{i} \geq y$ a_i \ge y.

¿Por qué es esto cierto?

Imagina que tenemos dos elementos de la matriz entre $x$ y $2 x$ , llamémoslos $y_{1} < y_{2}$ y_1<y_2.

y_{1} mod x = y_{1} - x y y_{2} mod x = y_{2} - x

y_1 \bmod x = y_1-x \text{ y } y_2 \bmod x = y_2-x

Y debido a que $y 1 < y 2$ y1<y2, así que $y_{1} mod x < y_{2} mod x$ y_1 \bmod x<y_2 \bmod x.

Así que solo nos importa el primer elemento en el rango $[x, 2 x]$ , y lo mismo para los rangos $[2 x, 3 x]$ [2x,3x], $[3 x, 4 x]$ [3x,4x]... Una solución fácil es primero precalcular $nxt(x)$ para cada $x$ de $0$ a $mx$ , y luego para cada $x$ iterar sobre todos sus múltiplos.

Requiere $O (mx lo g (mx) + precalcular)$ O(\text{mx}\log(\text{mx}) + \text{precalcular}), que es más que $O (5 \times 1 0^{9})$ O(5 \times 10^9), así que necesitamos una forma más rápida.

Para el precálculo, podemos usar un enfoque de dos punteros, así que es $O (mx)$ .

Y para encontrar $min (a_{i} mod x)$ \min(a_i \bmod x) para cada $x$ (iterando sobre ellos de mayor $x$ a menor), podemos ver que en lugar de iterar sobre todos los múltiplos de $x$ , solo podemos iterar sobre $p \cdot x$ p \cdot x donde $p$ es un número primo.

¿Por qué es esto suficiente?

Porque supongamos que queremos encontrar $min (a_{i} mod x)$ \min(a_i \bmod x), como dijimos antes, es $min (nxt (x) mod x$ \min(\text{nxt}(x) \bmod x , $min (a_{i} mod 2 x) mod x$ \min(a_i \bmod 2x) \bmod x , $min (a_{i} mod 3 x) mod x$ \min(a_i \bmod 3x) \bmod x , $min (a_{i} mod 4 x) mod x$ \min(a_i \bmod 4x) \bmod x , ...), podemos notar que $min (a_{i} mod 4 x)$ \min(a_i \bmod 4x) ya se ha computado en $min (a_{i} mod 2 x)$ \min(a_i \bmod 2x) y lo mismo para cualquier número no primo $z$ , $min (a_{i} mod z x)$ \min(a_i \bmod zx) ya se ha computado en todos sus factores primos.

Así que $min (a_{i} mod x) = min (nxt (0), nxt (x) mod x)$ \min(a_i \bmod x) = \min(\text{nxt}(0) , \text{nxt}(x) \bmod x) , $min (a_{i} mod 2 x) mod x$ \min(a_i \bmod 2x) \bmod x , $min (a_{i} mod 3 x) mod x$ \min(a_i \bmod 3x)\bmod x , $min (a_{i} mod 5 x) mod x$ \min(a_i \bmod 5x) \bmod x , ... ).

Pero, ¿es la complejidad lo suficientemente rápida?

Bueno, podemos calcular el número de operaciones que este método realiza usando un solo bucle, y descubrir que son aproximadamente $3 e 8$ operaciones.

La complejidad aproximada es $O (mx lo g (lo g (mx)))$ O(\text{mx}\log(\log(\text{mx}))), dejamos la prueba a su cargo.

Para encontrar todos los números primos hasta $mx$ , podemos usar la criba en $O (mx lo g (lo g (mx)))$ O(\text{mx}\log(\log(\text{mx}))).

Así que la complejidad total es $O (2 mx lo g (lo g (mx)) + q lo g (mx))$ O(2\text{mx}\log(\log(\text{mx})) + q\log(\text{mx})) que es lo suficientemente rápida para pasar.

#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";
    }
}

C++