Величні сегменти II#12333

Величні сегменти II (Розбір)

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

Запишіть просту факторизацію $k$ у вигляді

k = p_{1}^{e_{1}} \cdot p_{2}^{e_{2}} \dots p_{m}^{e_{m}} .

k = p_1^{e_1} \cdot p_2^{e_2} \cdots p_m^{e_m}.

$LCM$ підмасиву ділиться на $k$ тоді і тільки тоді, коли для кожної степені простого числа $p_{i}^{e_{i}}$ p_i^{e_i} існує принаймні один елемент у підмасиві, який ділиться на $p_{i}^{e_{i}}$ p_i^{e_i}. Тому, замість того, щоб безпосередньо працювати з $LCM$ , достатньо забезпечити, щоб кожна потрібна степінь простого числа з'являлася принаймні один раз у підмасиві.

Ми факторизуємо $k$ за допомогою пробного ділення і зберігаємо всі значення $p_{i}^{e_{i}}$ p_i^{e_i} в масиві $P$ . Кількість таких значень невелика (не більше $12$ ). Якщо $k = 1$ k=1, тоді кожен підмасив є дійсним, і відповідь просто

\frac{n ( n + 1 )}{2} .

\frac{n(n+1)}{2}.

Для загального випадку ми скануємо масив зліва направо. Для кожної збереженої степені простого числа $P [j]$ ми підтримуємо останній індекс, де з'явився елемент, який ділиться на $P [j]$ , позначений як $last [j]$ . Спочатку всі значення $last$ дорівнюють нулю. При обробці позиції $i$ , для кожного $j$ , такого що $a_{i}$ a_i ділиться на $P [j]$ , ми оновлюємо $last [j] = i$ \text{last}[j]=i. Нехай

id = j min last [j] .

\text{id} = \min_j \text{last}[j].

Всі підмасиви, що закінчуються на $i$ і починаються з будь-якої позиції $1 \leq l \leq id$ 1 \le l \le \text{id}, містять всі потрібні степені простих чисел і тому є дійсними, отже, ми додаємо $id$ до відповіді.

Це правильно, оскільки для фіксованої правої межі $i$ найменша можлива ліва межа, яка все ще містить всі потрібні степені простих чисел, є точною $min_{j} last [j]$ \min_j \text{last}[j]. Будь-який раніше початок лише додає додаткові елементи і зберігає дійсність. Кожен дійсний підмасив враховується точно один раз, на його правій межі.

Загальна складність становить $O (n \cdot ∣ P ∣ + t \cdot π (k))$ O(n \cdot |P| + t \cdot \pi(\sqrt{k})), де $∣ P ∣ \leq 13$ |P| \le 13, $π (n)$ - кількість простих чисел до $n$ включно, $max (k) = 1 0^{14}$ \max(k)=10^{14}, $π (1 0^{7}) = 664579$ \pi(10^7)=664579, отже, складність в числових термінах: $O (13 \times 2 \times 1 0^{6} + 6.6 \times 1 0^{7})$ O(13 \times 2 \times 10^6+6.6 \times 10^7), що приблизно дорівнює $O (9 \times 1 0^{7})$ O(9 \times 10^7) у найгіршому випадку.

Реалізація

#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)
#define double long double

using namespace std;

mt19937 rnd(time(0));

const int N = 2e6+9;

ll n,k,a[N];
bool s[5*N];
vector<int> v;
vector<ll> p;
int lst[20];

ll fp(ll x , ll y)
{
    if(y==0)
        return 1;
    ll z = fp(x,y/2);
    z*=z;
    if(y%2)
        z*=x;
    return z;
}

int main()
{
    d3
    for(int i = 2 ; 10000>i ; i++)
    {
        if(s[i])
            continue;
        for(int j = i*i ; 5*N>j ; j+=i)
            s[j]=1;
    }
    for(int i = 2 ; 5*N>i ; i++)
    {
        if(!s[i])
            v.pb(i);
    }
    int T = 1;
    cin >> T;
    while(T--)
    {
        p.clear();
        cin >> n >> k;
        for(int i = 1 ; n>=i ; i++)
            cin >> a[i];
        if(k==1)
        {
            cout << n*(n+1)/2 << "\n";
            continue;
        }
        for(auto it : v)
        {
            if(k==1)
                break;
            if(k%it)
                continue;
            ll e = 0;
            while(k%it==0)
            {
                k/=it;
                e++;
            }
            p.pb(fp(it,e));
        }
        if(k>1)
            p.pb(k);
        ll ans = 0;
        for(int8_t i = 0 ; 20>i ; i++)
            lst[i]=0;
        for(int i = 1 ; n>=i ; i++)
        {
            for(int8_t j = 0 ; p.size()>j ; j++)
            {
                if(a[i]%p[j]==0)
                    lst[j]=i;
            }
            int mn = i;
            for(int8_t j = 0 ; p.size()>j ; j++)
                mn=min(mn,lst[j]);
            ans+=mn;
        }
        cans
    }
}