Majestic Segments II#12333

Majestic Segments II (Editorial)

Problem Author:	De3b0o
Prepared by:	De3b0o
Edited by:	Hasan Saleh (MathModel)

Write the prime factorization of $k$ as

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

The $LCM$ of a subarray is divisible by $k$ if and only if, for every prime power $p_{i}^{e_{i}}$ p_i^{e_i}, there exists at least one element inside the subarray divisible by $p_{i}^{e_{i}}$ p_i^{e_i}. Therefore, instead of dealing with $LCM$ s directly, it is sufficient to ensure that each required prime power appears at least once inside the subarray.

We factorize $k$ using trial division and store all values $p_{i}^{e_{i}}$ p_i^{e_i} in an array $P$ . The number of such values is small (at most $12$ ). If $k = 1$ k=1, then every subarray is valid and the answer is simply

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

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

For the general case, we scan the array from left to right. For every stored prime power $P [j]$ , we maintain the last index where an element divisible by $P [j]$ appeared, denoted by $last [j]$ . Initially, all values of $last$ are zero. When processing position $i$ , for every $j$ such that $a_{i}$ a_i is divisible by $P [j]$ , we update $last [j] = i$ \text{last}[j]=i. Let

id = j min last [j] .

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

All subarrays ending at $i$ and starting at any position $1 \leq l \leq id$ 1 \le l \le \text{id} contain all required prime powers and are therefore valid, so we add $id$ to the answer.

This is correct because for a fixed right endpoint $i$ , the smallest possible left endpoint that still contains all required prime powers is exactly $min_{j} last [j]$ \min_j \text{last}[j]. Any earlier start only adds extra elements and preserves validity. Each valid subarray is counted exactly once, at its right endpoint.

The overall complexity is $O (n \cdot ∣ P ∣ + t \cdot π (k))$ O(n \cdot |P| + t \cdot \pi(\sqrt{k})). where $∣ P ∣ \leq 13$ |P| \le 13 , $π (n)$ is the count of primes upto $n$ inclusive , $max (k) = 1 0^{14}$ \max(k)=10^{14} , $π (1 0^{7}) = 664579$ \pi(10^7)=664579 thus complexity in numerical terms is : $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) which is roughly $O (9 \times 1 0^{7})$ O(9 \times 10^7) at worst case.

Implementation

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