Deebo-nun MathModel Ideal Hədiyyəsi#11857

Deebo-nun MathModel Ideal Hədiyyəsi (Həll təhlili)

Problem Müəllifi:	(De3b0o)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	(De3b0o)

Həll

Biz görürük ki, $b_{i} \cdot x - a_{i} = x - a_{i} mod x$ b_i \cdot x - a_i = x - a_i \bmod x , beləliklə, şərt $b_{i} \cdot x - a_{i} \leq c$ b_i \cdot x - a_i \le c eynidir $x - a_{i} mod x \leq c$ x - a_i \bmod x \le c , və biz bu şərtin bütün $i$ üçün doğru olmasını istəyirik, beləliklə, yalnız $x - a_{i} mod x$ x - a_i \bmod x -in maksimum dəyəri ilə maraqlanırıq, beləliklə, yalnız $a_{i} mod x$ a_i \bmod x-in minimum dəyəri ilə maraqlanırıq.

İndi bir tək sorğu üçün cavab, $x - min (a_{i} mod x) \leq c$ x - \min(a_i \bmod x) \le c olan ən böyük $x$ -dir.

Biz görə bilərik ki, $x$ $min (a_{1}, a_{2}, ...., a_{n}) + c$ \min(a_1,a_2,....,a_n) + c -dan böyük ola bilməz, və əgər $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)-dirsə, cavab $min (a_{1}, a_{2}, ..., a_{n}) + c$ \min(a_1,a_2,...,a_n) + c -dir.

Əks halda cavab $\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)-dir.

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

Beləliklə, əgər $1$ -dən $mx$ -ə qədər hər $x$ üçün $min (a_{i} mod x)$ \min(a_i \bmod x) -i tapmağın sehrli bir yolunu təsəvvür etsək, o zaman sorğuları asanlıqla cavablandıra bilərik (ikili axtarış və ya offline istifadə edərək).

İndi sehrli yol.

Bəzi $x$ üçün, $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 , və s.)-ə bərabərdir.

Burada $nxt(y)$ $a_{i}$ a_i-nin ən kiçikidir ki, $a_{i} \geq y$ a_i \ge y.

Niyə bu doğrudur?

Təsəvvür edin ki, massivdən $x$ və $2 x$ arasında iki element var, onları $y_{1} < y_{2}$ y_1<y_2 adlandıraq.

y_{1} mod x = y_{1} - x və y_{2} mod x = y_{2} - x

y_1 \bmod x = y_1-x \text{ və } y_2 \bmod x = y_2-x

Və çünki $y 1 < y 2$ y1<y2, beləliklə $y_{1} mod x < y_{2} mod x$ y_1 \bmod x<y_2 \bmod x.

Beləliklə, yalnız $[x, 2 x]$ aralığındakı ilk elementlə maraqlanırıq, eyni şey $[2 x, 3 x]$ [2x,3x], $[3 x, 4 x]$ [3x,4x] aralıqları üçün də keçərlidir... Asan bir həll, əvvəlcə $0$ -dan $mx$ -ə qədər $nxt(x)$ -i əvvəlcədən hesablamaqdır, sonra hər $x$ üçün bütün onun çoxluqlarını dövr etməkdir.

Bu $O (mx lo g (mx) + precalculate)$ O(\text{mx}\log(\text{mx}) + \text{precalculate}) tələb edir ki, bu da $O (5 \times 1 0^{9})$ O(5 \times 10^9)-dən çoxdur, buna görə daha sürətli bir yol lazımdır.

Əvvəlcədən hesablamaq üçün, sadəcə iki göstərici yanaşmasından istifadə edə bilərik, beləliklə bu $O (mx)$ -dir.

Və hər $x$ üçün $min (a_{i} mod x)$ \min(a_i \bmod x)-i tapmaq üçün (onları ən böyük $x$ -dən ən kiçikə doğru dövr edərək), biz görə bilərik ki, $x$ -in bütün çoxluqlarını dövr etmək əvəzinə, yalnız $p \cdot x$ p \cdot x-i dövr edə bilərik, burada $p$ bir asal ədəddir.

Niyə bu kifayətdir?

Çünki biz $min (a_{i} mod x)$ \min(a_i \bmod x)-i tapmaq istəyiriksə, əvvəlki kimi, bu $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 , ...)-dir, biz görə bilərik ki, $min (a_{i} mod 4 x)$ \min(a_i \bmod 4x) artıq $min (a_{i} mod 2 x)$ \min(a_i \bmod 2x)-də hesablanmışdır və hər hansı qeyri-asal ədəd $z$ üçün, $min (a_{i} mod z x)$ \min(a_i \bmod zx) artıq bütün asal faktorlarında hesablanmışdır.

Beləliklə, $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 , ...).

Amma mürəkkəblik kifayət qədər sürətlidirmi?

Yaxşı, bu metodun bir döngü istifadə edərək əməliyyat sayını hesablaya bilərik və təxminən $3 e 8$ əməliyyat olduğunu öyrənirik.

Təxminən mürəkkəblik $O (mx lo g (lo g (mx)))$ O(\text{mx}\log(\log(\text{mx})))-dir, sübutu sizə buraxırıq.

$mx$ -ə qədər bütün asal ədədləri tapmaq üçün, $O (mx lo g (lo g (mx)))$ O(\text{mx}\log(\log(\text{mx})))-də süzgəc istifadə edə bilərik.

Beləliklə, ümumi mürəkkəblik $O (2 mx lo g (lo g (mx)) + q lo g (mx))$ O(2\text{mx}\log(\log(\text{mx})) + q\log(\text{mx}))-dir ki, bu da keçmək üçün kifayət qədər sürətlidir.

#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 << "BƏLİ" << "\n";
#define no cout << "XAHİŞ ETMİR" << "\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++