求一个区间里的一个x，这个x与这区间里面的所有数都互质

链接：https://ac.nowcoder.com/acm/contest/301/H
来源：牛客网

题描述

小乐乐上了一节数学课，数学老师讲的很好，小乐乐听的也如痴如醉。
小乐乐听了老师的讲解，知道了什么是素数，现在他想做几个习题。
现在题目来了：
首先我们先定义孤独的数：在一个区间中的一个数字x,如果他与这个区间中的任何数都互质，那么他就是孤独的数。
我们给定一个序列，然后接下来会有多次询问，对于每次询问，给定两个整数l, r,我想知道对于(a[l], a[l + 1], ...., a[r])区间来说中有多少孤独的数。

分析：戴普，现在先当模板

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <vector>

const int MaxN = 1e5;

using namespace std;

int n, m, tot;

int a[MaxN + ], pri[MaxN + ];

int pre[MaxN + ], last[MaxN + ], c[MaxN + ];

vector <int> V[MaxN + ], g[MaxN + ];

int res[MaxN + ];

bool vis[MaxN + ];

struct NODE {

    int l, r, id;

    bool operator < (const NODE A) const {

        return l < A.l;

    }

}query[MaxN + ], seg[MaxN + ];

bool cmp(NODE A, NODE B)

{

    return A.r < B.r;

}

void Init()

{

    for (int i = ; i <= MaxN; i++) {

        if(!vis[i]) pri[++tot] = i;

        for (int j = ; j <= tot && i * pri[j] <= MaxN; j++) {

            vis[i * pri[j]] = ;

            if(i % pri[j] == ) break;

        }

    }

    for (int i = ; i <= tot; i++) {

        for (int j = pri[i]; j <= MaxN; j += pri[i]) V[j].push_back(pri[i]);

    }

}

void Add(int x, int w)

{

    if(x == ) return;

    for (int i = x; i <= MaxN; i += (i & (-i))) c[i] += w;

}

int Sigma(int x)

{

    int res = ;

    for (int i = x; i > ; i -= (i & (-i))) res += c[i];

    return res;

}

int main()

{

    Init();

    while(~scanf("%d%d", &n, &m)) {

        memset(c, , sizeof(c)); memset(pre, , sizeof(pre));

        g[n + ].clear();

        for (int i = ; i <= n; i++) scanf("%d", &a[i]), g[i].clear();

        for (int i = ; i <= n; i++) {

            if(a[i] == ) {

                seg[i].l = ;

            }

            else {

                int Max = ;

                for (int v : V[a[i]]) Max = max(Max, pre[v]);

                seg[i].l = Max;

                for (int v : V[a[i]]) pre[v] = i;

            }

        }

        for (int i = ; i <= MaxN; i++) last[i] = n + ;

        for (int i = n; i >= ; i--) {

            if(a[i] == ) seg[i].r = n + ;

            else {

                int Min = n + ;

                for (int v : V[a[i]]) Min = min(Min, last[v]);

                seg[i].r = Min;

                for (int v : V[a[i]]) last[v] = i;

            }

        }

        for (int i = ; i <= n; i++) g[seg[i].r].push_back(i);

        for (int i = ; i <= m; i++) scanf("%d%d", &query[i].l, &query[i].r), query[i].id = i;

        sort (query + , query + m + , cmp);

        int l = ;

        for (int i = ; i <= m; i++) {

            while(l +  <= n && l +  <= query[i].r) {

                Add(seg[l + ].l, );

                for (int v : g[l + ]) {

                    Add(seg[v].l, -); Add(v, );

                }

                l++;

            }

            res[query[i].id] = query[i].r - query[i].l +  - Sigma(query[i].r) + Sigma(query[i].l - );

        }

        for (int i = ; i <= m; i++) printf("%d\n", res[i]);

    }

    return ;

}

#include <iostream>

#include <cstdio>

#include <cmath>

#include <string>

#include <cstring>

#include <algorithm>

#include <limits>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#define lowbit(x) ( x&(-x) )

#define pi 3.141592653589793

#define e 2.718281828459045

using namespace std;

typedef unsigned long long ull;

typedef long long ll;

const int N = 1e5+;

int w[N],l[N],r[N];//l[i],r[i]保存第i个数的质因子出现的最左位置以及最右位置

vector<int>V[N];//V[i]存储的是j，其中r[j]=i

vector<int>have[N],VPrime;//have[i]存储的是数字i分解的质因子，VPrime存储的是[1,200000]的素数

int ans[N];//存储结果

int flag[N];

struct node

{

    int left,right,id;

}p[N];

int cmp(node aa,node bb)

{

    return aa.right<bb.right;

}

int ar[N];

int lowb(int t)

{

    return t&(-t);

}

void add(int i,int v)

{

    if(i==) return;

    for(;i<N;ar[i]+=v,i+=lowb(i));

}

int sum(int i)

{

    int s=;

    for(;i>;s+=ar[i],i-=lowb(i));

    return s;

}

void getHave(int index,int v)

{

    int i=;

    while(v>&&i<VPrime.size())

    {

        if(VPrime[i]*VPrime[i]>v)

        {

            have[index].push_back(v);

            break;

        }

        if(i<VPrime.size()&& v%VPrime[i]==)

        {

            have[index].push_back(VPrime[i]);

        }

        while(i<VPrime.size()&& v%VPrime[i]==)

        {

            v/=VPrime[i];

        }

        i++;

    }

}

bool prime[N];

void init()

{

    int i,j;

    memset(prime,,sizeof(prime));

    prime[]=prime[]=;

    for(i=;i<=N-;i++)

        for(j=;i*j<=N-;j++)

        {

            prime[i*j]=;

        }

    VPrime.clear();

    for(i=;i<=N-;i++)

    {

        if(prime[i]==)

            VPrime.push_back(i);

    }

    for(i=;i<N;i++)

    {

        have[i].clear();

    }

    for(i=;i<N;i++)

    {

        getHave(i,i);

    }

}

void init2(int n)//计算出l数组,r数组以及V[]

{

    for(int i=;i<=n;i++)

    {

        V[i].clear();

    }

    memset(l,,sizeof(l));

    memset(r,,sizeof(r));

    memset(flag,,sizeof(flag));

    for(int i=;i<=n;i++)

    {

        int left=;

        for(int j=;j<have[w[i]].size();j++)

        {

            left=max(left,flag[have[w[i]][j]]);

        }

        l[i]=left;

        for(int j=;j<have[w[i]].size();j++)

        {

            flag[have[w[i]][j]]=i;

        }

    }

    for(int i=;i<N;i++)//这里要初始化为n+1

    {flag[i]=n+;}

    for(int i=n;i>=;i--)

    {

        int right=n+;

        for(int j=;j<have[w[i]].size();j++)

        {

            right=min(right,flag[have[w[i]][j]]);

        }

        r[i]=right;

        for(int j=;j<have[w[i]].size();j++)

        {

            flag[have[w[i]][j]]=i;

        }

    }

    for(int i=;i<=n;i++)

    {

        V[r[i]].push_back(i);

    }

}

int main()

{

    int i,j,k;

    int n,m,t;

    init();

    while(scanf("%d%d",&n,&m)!=EOF&&!(n==&&m==))

    {

        for(i=;i<=n;i++)

        {

            scanf("%d",&w[i]);

        }

        init2(n);

        for(i=;i<=m;i++)

        {

            scanf("%d%d",&p[i].left,&p[i].right);

            p[i].id=i;

        }

        sort(p+,p++m,cmp);

        memset(ar,,sizeof(ar));

        i=;

        for(j=;j<=m;j++)

        {

            while(i<=p[j].right)

            {

                add(l[i],);//将左边notFit的+1

                for(k=;k<V[i].size();k++)

                {

                    add(l[V[i][k]],-);//将左边跟右边同时notFit的-1，去掉重复

                    add(V[i][k],);//将右边notFit的+1

                }

                i++;

            }

            int notFit=sum(p[j].right)-sum(p[j].left-);

            ans[p[j].id]=p[j].right-p[j].left+-notFit;

        }

        for(i=;i<=m;i++)

        {

            printf("%d\n",ans[i]);

        }

    }

    return ;

}

巴特西

求一个区间里的一个x，这个x与这区间里面的所有数都互质

题描述

最新文章

热门文章