Ідеальний подарунок для MathModel від Deebo#11857

Ідеальний подарунок для MathModel від Deebo (Розбір)

Автор проблеми:	(De3b0o)
Підготовлено:	Hasan Saleh (MathModel)
Редаговано:	(De3b0o)

Рішення

Ми помічаємо, що $b_{i} \cdot x - a_{i} = x - a_{i} mod x$ b_i \cdot x - a_i = x - a_i \bmod x , тому умова $b_{i} \cdot x - a_{i} \leq c$ b_i \cdot x - a_i \le c є такою ж, як $x - a_{i} mod x \leq c$ x - a_i \bmod x \le c , і оскільки ми хочемо, щоб ця умова була істинною для всіх $i$ , то нас цікавить лише максимальне значення $x - a_{i} mod x$ x - a_i \bmod x , отже, нас цікавить лише мінімальне значення $a_{i} mod x$ a_i \bmod x.

Тепер відповідь на один запит - найбільше $x$ , таке що $x - min (a_{i} mod x) \leq c$ x - \min(a_i \bmod x) \le c.

Ми можемо бачити, що $x$ не може бути більшим за $min (a_{1}, a_{2}, ...., a_{n}) + c$ \min(a_1,a_2,....,a_n) + c , і якщо $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), то відповідь - $min (a_{1}, a_{2}, ..., a_{n}) + c$ \min(a_1,a_2,...,a_n) + c.

В іншому випадку відповідь є $\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))

Отже, якщо ми уявимо, що у нас є магічний спосіб знайти, для кожного $x$ від $1$ до $mx$ , $min (a_{i} mod x)$ \min(a_i \bmod x) , тоді ми можемо легко відповідати на запити (використовуючи бінарний пошук або офлайн).

Тепер про магічний спосіб.

Для деякого $x$ , $min (a_{i} mod x)$ \min(a_i \bmod x) дорівнює $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 , і так далі ...)

Де $nxt(y)$ - найменше $a_{i}$ a_i, де $a_{i} \geq y$ a_i \ge y.

Чому це правда?

Уявіть, що у нас є два елементи з масиву між $x$ та $2 x$ , назвемо їх $y_{1} < y_{2}$ y_1<y_2.

y_{1} mod x = y_{1} - x та y_{2} mod x = y_{2} - x

y_1 \bmod x = y_1-x \text{ та } y_2 \bmod x = y_2-x

І оскільки $y 1 < y 2$ y1<y2, то $y_{1} mod x < y_{2} mod x$ y_1 \bmod x<y_2 \bmod x.

Отже, нас цікавить лише перший елемент у діапазоні $[x, 2 x]$ , і те ж саме для діапазонів $[2 x, 3 x]$ [2x,3x], $[3 x, 4 x]$ [3x,4x] ... Легке рішення - спочатку попередньо обчислити $nxt(x)$ для кожного $x$ від $0$ до $mx$ , а потім для кожного $x$ ітерувати по всіх його кратних.

Це вимагає $O (mx lo g (mx) + precalculate)$ O(\text{mx}\log(\text{mx}) + \text{precalculate}), що більше ніж $O (5 \times 1 0^{9})$ O(5 \times 10^9), тому нам потрібен швидший спосіб.

Для попереднього обчислення ми можемо просто використовувати підхід з двома вказівниками, тому це $O (mx)$ .

А щоб знайти $min (a_{i} mod x)$ \min(a_i \bmod x) для кожного $x$ (ітерація по них від найбільшого $x$ до найменшого), ми можемо помітити, що замість ітерації по всіх кратних $x$ , ми можемо ітерувати лише по $p \cdot x$ p \cdot x, де $p$ - просте число.

Чому цього достатньо?

Бо, припустимо, ми хочемо знайти $min (a_{i} mod x)$ \min(a_i \bmod x), як ми сказали раніше, це $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 , ... ), ми можемо помітити, що $min (a_{i} mod 4 x)$ \min(a_i \bmod 4x) вже обчислено в $min (a_{i} mod 2 x)$ \min(a_i \bmod 2x) і те ж саме для будь-якого непростого числа $z$ , $min (a_{i} mod z x)$ \min(a_i \bmod zx) вже обчислено у всіх його простих множниках.

Отже, $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 , ... ).

Але чи достатня швидкість складності?

Ну, ми можемо обчислити кількість операцій, які цей метод виконує, використовуючи один цикл, і виявити, що це приблизно $3 e 8$ операцій.

Приблизна складність - $O (mx lo g (lo g (mx)))$ O(\text{mx}\log(\log(\text{mx}))), ми залишаємо доказ вам.

Щоб знайти всі прості числа до $mx$ , ми можемо використовувати решето за $O (mx lo g (lo g (mx)))$ O(\text{mx}\log(\log(\text{mx}))).

Отже, загальна складність $O (2 mx lo g (lo g (mx)) + q lo g (mx))$ O(2\text{mx}\log(\log(\text{mx})) + q\log(\text{mx})), що достатньо швидко, щоб пройти.

#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++