2017 USP Try-outs C. Coprimes

Portal ：Coprimes

The question ： Give you a length of $n$ Array of , ask $l$ To $r$ Whether there are mutual prime pairs between positions $(a[i],a[j])=1(i\ne j)$
For each location $l$, We can find the smallest $r$, bring $[l,r]$ There are coprime pairs between .
With $l$ The increase of ,$r$ It must increase , So we can consider taking a ruler . When the right endpoint enters and the left endpoint exits , We try to maintain the number of non coprime pairs in the interval $pair$.
about $\mu (x)\ne 0$ Of $x$, We use it $cnt[x]$ maintain , Among the factors of how many numbers are in the interval $x$, then , Did not enter a right endpoint $r$ when , Then each $d|a[r]$ And $\mu (d)\ne 0$ And $d\ne 1$ Of $d$ Yes $pair$ The contribution of $-\mu (d)cnt[d]$, Add this contribution to $pair$ In go to , Empathy , Exit one endpoint after another , Take this contribution from $pair$ Subtract from .

In short , Build a bucket ,$cnt[x]$ To maintain $x$ Number of multiples , Then in the set and $a[x]$ The number of non reciprocal primes is equal to
$$\sum _{d|a[i],d\ne 1}-\mu (d)cnt[d]$$
because 1 It cannot be used as a common factor, so it can be excluded $cnt[1]$ It makes no sense , We skip 1, All the following numbers should be reversed

#include<bits/stdc++.h>
using namespace std;
int nxt[500005];
bool vis[10000005];
int pri[1000005];
int mo[1000005];
int tot=0;
void init(int n)
{
    
    memset(vis,0,sizeof(vis));
    mo[1]=1;
    for(int i=2;i<=n;i++)
    {
    
        if(!vis[i])pri[++tot]=i,mo[i]=-1;
        for(int j=1;j<=tot&&pri[j]*i<=n;j++)
        {
    
            vis[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
    
                mo[i*pri[j]]=0;
                break;
            }
            else mo[i*pri[j]]=mo[i]*-1;
        }
    }
}
int nowans=0;
int CNT[500005];
int a[500005];
void addcnt(int id,int w)
{
    
    for(int i=1;i*i<=a[id];i++)
    {
    
        if(a[id]%i==0)
        {
    
            if(i*i==a[id])CNT[i]+=w;
            else
            {
    
                CNT[i]+=w;
                CNT[a[id]/i]+=w;
            }
        }
    }
}
void add(int id,int w)
{
    
    for(int i=1;i*i<=a[id];i++)
    {
    
        if(a[id]%i==0)
        {
    
            if(i*i==a[id])
            {
    
                nowans+=mo[i]*w*CNT[i];
            }
            else
            {
    
                nowans+=mo[i]*w*CNT[i];
                nowans+=mo[a[id]/i]*w*CNT[a[id]/i];
            }

        }
    }


}
int main()
{
    
    init(500000);
    mo[1]=0;
    int N,M;
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)scanf("%d",&a[i]);

    int R=0;
    for(int l=1;l<=N;l++)
    {
    
        while(nowans<=0&&R<N)
        {
    
            add(++R,1);
            addcnt(R,1);
            nowans+=R-l;
        }
        if(nowans>0)nxt[l]=R;
        else nxt[l]=-1;
        nowans-=R-l;
        addcnt(l,-1);
        add(l,-1);
    }
    for(int i=1;i<=M;i++)
    {
    
        int l,r;
        scanf("%d%d",&l,&r);
        if(nxt[l]!=-1&&nxt[l]<=r)printf("S\n");
        else printf("N\n");
    }
    return 0;
}