HDU6287 ／BZOJ 5358 口算训练

爱被打了一巴掌 2021-09-20 11:40 189阅读 0赞

[传送门][Link 1]

题解：由唯一分解可以知道每个数都能表示成素数的乘积，因此我们只要判断\[l,r\]区间内是否出现过d分解成素数后各个素数的次数。用主席树维护之前l-1版本的数，和r版本的树，前后做差就能判断是否满足要求。

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <map>
    #include <queue>
    #include <vector>
    #include <cstring>
    #include <iomanip>
    #include <set>
    #include<ctime>
    //CLOCKS_PER_SEC
    #define se second
    #define fi first
    #define ll long long
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define Pii pair<int,int>
    #define Pli pair<ll,int>
    #define ull unsigned long long
    #define pb push_back
    #define fio ios::sync_with_stdio(false);cin.tie(0)
    const double Pi=3.14159265;
    const int N=1e5+10;
    const ull base=163;
    const int INF=0x3f3f3f3f;
    using namespace std;
    bool notpri[N];
    int pri[N],id[N],tot=0;
    int root[N];
    struct node {
        int l,r,sum;
    }T[N*40];
    int cnt=0;
    inline int read(){
        int x=0;char ch=getchar();
        while (ch<'0'||ch>'9') ch=getchar();
        while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
        return x;
    }
    void getprime(){
        for(int i=2;i<=1e5+5;i++){
            if(!notpri[i])pri[++tot]=i,id[i]=tot;
            for(int j=1;j<=tot&&pri[j]*i<1e5+5;j++){
                notpri[pri[j]*i]=1;
                if(i%pri[j]==0)break;
            }
        }
    }
    void update(int l,int r,int &x,int pos,int v){
        T[++cnt]=T[x],x=cnt;
        if(l==r){T[x].sum+=v;return ;}
        int m=(l+r)>>1;
        if(pos<=m)update(l,m,T[x].l,pos,v);
        else update(m+1,r,T[x].r,pos,v);
    }
    bool query(int l,int r,int x,int y,int pos,int v){
        if(l==r){
        return T[y].sum-T[x].sum>=v;}
        int m=(l+r)>>1;
        if(pos<=m)return query(l,m,T[x].l,T[y].l,pos,v);
        else return query(m+1,r,T[x].r,T[y].r,pos,v);
    }
    int main(){
        getprime();
        int t,n,m,x,l,r,k,num,flag;
        scanf("%d",&t);
        while(t--){
            cnt=0; n=read(),m=read();
            for(int i=1;i<=n;++i){
                root[i]=root[i-1];
                x=read();
                for(int j=1;j<=tot&&pri[j]*pri[j]<=x;++j){
         
                    num=0;
                    while(x%pri[j]==0)x/=pri[j],++num;
                    if(num)update(1,tot,root[i],j,num);
                }
    　　　　　　　if(x!=1)update(1,tot,root[i],id[x],1);
            }
            for(int i=1;i<=m;++i){
                l=read(),r=read(),k=read();
                flag=0;
                for(int j=1;j<=tot&&pri[j]*pri[j]<=k;++j){
         
                    num=0;
                    while(k%pri[j]==0)k/=pri[j],++num;
                    if(num&&!query(1,tot,root[l-1],root[r],j,num))flag=1;
                    if(flag)break;
                }
    　　　　　　　if(k!=1&&!query(1,tot,root[l-1],root[r],id[k],1))flag=1;
                if(flag)puts("No");
                else puts("Yes");
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Mrleon/p/9101251.html

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=5358