Le cadeau idéal de MathModel de Deebo#11857

Le cadeau idéal de MathModel de Deebo (Corrigé)

Auteur du problème:	(De3b0o)
Préparé par:	Hasan Saleh (MathModel)
Édité par:	(De3b0o)

Solution

Nous remarquons que $b_{i} \cdot x - a_{i} = x - a_{i} mod x$ b_i \cdot x - a_i = x - a_i \bmod x , donc la condition $b_{i} \cdot x - a_{i} \leq c$ b_i \cdot x - a_i \le c est la même que $x - a_{i} mod x \leq c$ x - a_i \bmod x \le c , et puisque nous voulons que cette condition soit vraie pour tous les $i$ , nous ne nous soucions que de la valeur maximale de $x - a_{i} mod x$ x - a_i \bmod x , donc nous ne nous soucions que de la valeur minimale de $a_{i} mod x$ a_i \bmod x.

Maintenant, la réponse pour une seule requête est le plus grand $x$ tel que $x - min (a_{i} mod x) \leq c$ x - \min(a_i \bmod x) \le c.

Nous pouvons voir que $x$ ne peut pas être plus grand que $min (a_{1}, a_{2}, ...., a_{n}) + c$ \min(a_1,a_2,....,a_n) + c , et 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) alors la réponse est $min (a_{1}, a_{2}, ..., a_{n}) + c$ \min(a_1,a_2,...,a_n) + c.

Sinon, la réponse est $\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))

Donc, si nous imaginons que nous avons un moyen magique de trouver, pour chaque $x$ de $1$ à $mx$ , $min (a_{i} mod x)$ \min(a_i \bmod x) , alors nous pouvons répondre aux requêtes facilement (en utilisant une recherche binaire ou hors ligne).

Maintenant pour le moyen magique.

Pour un certain $x$ , $min (a_{i} mod x)$ \min(a_i \bmod x) est égal à $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 , et ainsi de suite ...)

Où $nxt(y)$ est le plus petit $a_{i}$ a_i tel que $a_{i} \geq y$ a_i \ge y.

Pourquoi est-ce vrai ?

Imaginez que nous avons deux éléments du tableau entre $x$ et $2 x$ , appelons-les $y_{1} < y_{2}$ y_1<y_2.

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

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

Et parce que $y 1 < y 2$ y1<y2, donc $y_{1} mod x < y_{2} mod x$ y_1 \bmod x<y_2 \bmod x.

Donc nous ne nous soucions que du premier élément dans la plage $[x, 2 x]$ , et c'est la même chose pour les plages $[2 x, 3 x]$ [2x,3x], $[3 x, 4 x]$ [3x,4x] ... Une solution facile consiste à d'abord pré-calculer $nxt(x)$ pour chaque $x$ de $0$ à $mx$ , puis pour chaque $x$ itérer sur tous ses multiples.

Cela nécessite $O (mx lo g (mx) + pr e ˊ -calcul)$ O(\text{mx}\log(\text{mx}) + \text{pré-calcul}), ce qui est plus que $O (5 \times 1 0^{9})$ O(5 \times 10^9), donc nous avons besoin d'un moyen plus rapide.

Pour le pré-calcul, nous pouvons simplement utiliser une approche à deux pointeurs, donc c'est $O (mx)$ .

Et pour trouver $min (a_{i} mod x)$ \min(a_i \bmod x) pour chaque $x$ (en itérant de la plus grande valeur de $x$ à la plus petite), nous pouvons voir qu'au lieu d'itérer sur tous les multiples de $x$ , nous pouvons seulement itérer sur $p \cdot x$ p \cdot x où $p$ est un nombre premier.

Pourquoi cela suffit-il ?

Parce que supposons que nous voulons trouver $min (a_{i} mod x)$ \min(a_i \bmod x), comme nous l'avons dit plus tôt, c'est $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 , ... ), nous pouvons remarquer que $min (a_{i} mod 4 x)$ \min(a_i \bmod 4x) est déjà calculé dans $min (a_{i} mod 2 x)$ \min(a_i \bmod 2x) et c'est la même chose pour tout nombre non premier $z$ , $min (a_{i} mod z x)$ \min(a_i \bmod zx) est déjà calculé dans tous ses facteurs premiers.

Donc $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 , ... ).

Mais la complexité est-elle suffisamment rapide ?

Eh bien, nous pouvons calculer le nombre d'opérations que cette méthode effectue en utilisant une seule boucle, et découvrir qu'il y a environ $3 e 8$ opérations.

La complexité approximative est $O (mx lo g (lo g (mx)))$ O(\text{mx}\log(\log(\text{mx}))), nous vous laissons la preuve.

Pour trouver tous les nombres premiers jusqu'à $mx$ , nous pouvons utiliser le crible en $O (mx lo g (lo g (mx)))$ O(\text{mx}\log(\log(\text{mx}))).

Donc, la complexité totale est $O (2 mx lo g (lo g (mx)) + q lo g (mx))$ O(2\text{mx}\log(\log(\text{mx})) + q\log(\text{mx})) ce qui est suffisamment rapide pour passer.

#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 << "OUI" << "\n";
#define no cout << "NON" << "\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++