Majestik Seqmentlər II#12333

Majestik Seqmentlər II (Həll təhlili)

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

$k$ -nın əsas faktorizasiyasını aşağıdakı kimi yazın:

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}.

Bir alt massivdəki $LCM$ , yalnız $k$ -ya bölünürsə, hər bir əsas güc $p_{i}^{e_{i}}$ p_i^{e_i} üçün alt massivdə $p_{i}^{e_{i}}$ p_i^{e_i}-yə bölünən ən azı bir elementin olması lazımdır. Buna görə də, $LCM$ -lə birbaşa məşğul olmaq əvəzinə, tələb olunan hər bir əsas gücün alt massivdə ən azı bir dəfə görünməsini təmin etmək kifayətdir.

Biz $k$ -nı sınaq bölməsi ilə faktorizasiya edirik və bütün $p_{i}^{e_{i}}$ p_i^{e_i} dəyərlərini $P$ massivində saxlayırıq. Belə dəyərlərin sayı azdır (ən çox $12$ ). Əgər $k = 1$ k=1-dirsə, onda hər bir alt massiv etibarlıdır və cavab sadəcə olaraq

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

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

Ümumi halda, massivdən soldan sağa skan edirik. Saxlanılan hər bir əsas güc $P [j]$ üçün, $P [j]$ -yə bölünən bir elementin göründüyü son indeksi saxlayırıq, bu $last [j]$ ilə göstərilir. Başlanğıcda, $last$ -ın bütün dəyərləri sıfırdır. $i$ mövqesini emal edərkən, $a_{i}$ a_i-nin $P [j]$ -yə bölündüyü hər bir $j$ üçün $last [j] = i$ \text{last}[j]=i-ni yeniləyirik. Tutaq ki,

id = j min last [j] .

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

$i$ -də bitən və istənilən $1 \leq l \leq id$ 1 \le l \le \text{id} mövqesindən başlayan bütün alt massivlər tələb olunan bütün əsas gücləri ehtiva edir və buna görə də etibarlıdır, buna görə də cavaba $id$ əlavə edirik.

Bu doğrudur, çünki sabit sağ ucu $i$ üçün, hələ də bütün tələb olunan əsas gücləri ehtiva edən ən kiçik sol ucu dəqiq $min_{j} last [j]$ \min_j \text{last}[j]-dir. Hər hansı bir əvvəlki başlanğıc yalnız əlavə elementlər əlavə edir və etibarlılığı qoruyur. Hər etibarlı alt massiv yalnız bir dəfə, sağ ucunda sayılır.

Ümumi mürəkkəblik $O (n \cdot ∣ P ∣ + t \cdot π (k))$ O(n \cdot |P| + t \cdot \pi(\sqrt{k}))-dir. burada $∣ P ∣ \leq 13$ |P| \le 13 , $π (n)$ $n$ -ə qədər olan asal ədədlərin sayıdır, $max (k) = 1 0^{14}$ \max(k)=10^{14} , $π (1 0^{7}) = 664579$ \pi(10^7)=664579 buna görə də ədədi terminlərdə mürəkkəblik: $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), bu da ən pis halda təxminən $O (9 \times 1 0^{7})$ O(9 \times 10^7)-dir.

İcra

#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)
#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
    }
}