Root Value#13065

Root Value (Editorial)

solution:

First, for an integer $x$ , let it's prime factorization be:

x = p_{1}^{α_{1}} \cdot p_{2}^{α_{2}} \times ... \times p_{n}^{α_{n}}

x = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \times ... \times p_n^{\alpha_n}

For an integer $m$ , $m x = x^{\frac{1}{m}}$ \sqrt[m]{x} = x^{\frac{1}{m}} , so

m x = p_{1}^{\frac{α _{1}}{m}} \times p_{2}^{\frac{α _{2}}{m}} \times ... \times p_{n}^{\frac{α _{n}}{m}}

\sqrt[m]{x} = p_1^{\frac{\alpha_1}{m}} \times p_2^{\frac{\alpha_2}{m}} \times ... \times p_n^{\frac{\alpha_n}{m}}

So $m x$ \sqrt[m]{x} would be a natural number if and only if $m$ is a common divisor of $α_{1}, α_{2}, ..., α_{n}$ \alpha_1 , \alpha_2 , ... , \alpha_n.

Since we need the maximum $m$ , the answer would be $g cd (α_{1}, α_{2}, ..., α_{n})$ \gcd(\alpha_1 , \alpha_2 , ... , \alpha_n) , where $α_{i}$ \alpha_i is the power of the $i_{th}$ i_{\text{th}} prime.

Now to find $m$ for a range , we know that

a_{l} \times a_{l + 1} \times ... \times a_{r} = p_{1}^{α_{l, 1} + α_{l + 1, 1} + ... + α_{r, 1}} \times ... \times p_{n}^{α_{l, n} + α_{l + 1, n} + ... + α_{r, n}}

a_l \times a_{l+1} \times ... \times a_r = p_1^{\alpha_{l,1} + \alpha_{l+1,1}+...+\alpha_{r,1}} \times ... \times p_n^{\alpha_{l,n} + \alpha_{l+1,n}+...+\alpha_{r,n}}

where $α_{i, j}$ \alpha_{i,j} is the power of the $j_{th}$ j_{\text{th}} prime in the $i_{th}$ i_{\text{th}} number.

Since $a_{i} \leq 200$ a_i \le 200, there are at most $47$ prime numbers. Let $pre [i] [j]$ \mathsf{pre}[i][j] be the prefix sum until index $i$ for the $j_{th}$ j_{\text{th}} prime.

The answer for a query ( $l, r$ ) would be:

$g cd (pre [r] [1] - pre [l - 1] [1], pre [r] [2] - pre [l - 1] [2], ..., pre [r] [47] - pre [l - 1] [47])$ \gcd(\mathsf{pre}[r][1] - \mathsf{pre}[l-1][1] , \mathsf{pre}[r][2] - \mathsf{pre}[l-1][2] , ... , \mathsf{pre}[r][47] - \mathsf{pre}[l-1][47])

Time Complexity : $O (47 \cdot (n + q))$ \mathcal{O}(47\cdot(n + q)).

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define F first
#define S second
using namespace std;
const int N = 2e5 + 1;
const int M = 1e9 + 7;
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    vector<int>primes;
    primes.push_back(2);
    for(int i=3;i<=200;i++)
    {
        bool ok = 1;
        for(int j=2;j*j<=i;j++)
        {
            if(i % j == 0)
            ok = 0;
        }
        if(ok)
        primes.push_back(i);
    };
    int tc = 1;
    cin>>tc;
    while(tc--)
    {
        int n,q;
        cin>>n>>q;
        int a[n+1] , pre[n+1][primes.size() + 1];
        memset(pre,0,sizeof pre);
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            for(int j=0;j<primes.size();j++)
            {
                while(a[i] % primes[j] == 0)
                {
                    pre[i][j]++;
                    a[i] /= primes[j];
                }
            }
        }
        for(int j=0;j<primes.size();j++)
        {
            for(int i=1;i<=n;i++)
            {
                pre[i][j] += pre[i-1][j];
            }
        }
        while(q--)
        {
            int l,r;
            cin>>l>>r;
            int ans = 0;
            for(int j=0;j<primes.size();j++)
            ans = __gcd(ans , pre[r][j] - pre[l-1][j]);
            cout<<ans<<endl;
        }
    }
}