打了一天的数据结构,感觉码力上升的很快,而且也学会了许多方法,但总体来说今天大部分的题很多都是看完题解以后才会的,无论怎么想也想不出来,还是要提高一下想题的能力,不要走神,不要急躁,仔细思考,不要颓废,还是要抓紧数据结构题的暴力,一般都很多,所以想不出正解一定要打暴力啊。
\(A\)
求区间 \(lcm\)。
对于 \(lcm\) 的数学性质的分析,我们发现我们只需要对于一个数每一个质因子(质数,质数的次幂在此均算质因子)在之前的出现位置上除以一个他的质数,(即在形如 \(p^k\) 的上一次出现的位置除去一个 \(p\)),就可以保证将重复的部分除去了(设 \(i<j\),如果 \(p^k \mid a_i \land p^{k+1} \mid a_j\),那么我们将在处理到 \(j\) 时,对于 \(i\) 位置的 \(p\) 的 \([1,k]\) 次方,除去 \(k\) 个 \(p\),我们再将 \(p^{k+1}\) 插入 \(j\) 位置,这样保证当区间左端点小于 \(i\) 时,即我们要求的 \(lcm\) 的元素包含 \(a_i\) 时,可以除去多余元素,当不包含时,保留这部分答案),那么我们只需要处理 \([l,r]\) 的积即可,我们发现如果离线,我们可以处理到区间右端点时统计答案,但本题强制在线,所以我们用主席树来维护。
\(code\)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define lson(rt) (tree[rt].ls)
#define rson(rt) (tree[rt].rs)
using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
int root[N];
int pos[N<<1];
int a[N],n,Q;
long long ans=0;
struct Prisident_Tree{
struct Pri{
int ls,rs,sum;
Pri(){ls=0,rs=0,sum=1;}
}tree[40000000];
int tot;
void pushup(int rt){tree[rt].sum=(1ll*tree[lson(rt)].sum*tree[rson(rt)].sum%mod);}
int insert(int rt,int l,int r,int pos,long long val){
int k=++tot;
tree[k]=tree[rt];
if(l==r){
tree[k].sum=1ll*tree[rt].sum*val%mod;
return k;
}
int mid=(l+r)>>1;
if(pos<=mid)lson(k)=insert(lson(rt),l,mid,pos,val);
else rson(k)=insert(rson(rt),mid+1,r,pos,val);
pushup(k);
return k;
}
long long ask(int rt,int l,int r,int pos){
if(l>=pos)return 1ll*tree[rt].sum;
if(r<pos)return 1;
int mid=(l+r)>>1;
return 1ll*ask(lson(rt),l,mid,pos)*ask(rson(rt),mid+1,r,pos)%mod;
}
}T;
int prime[N<<1],not_prime[N<<1],min_prime[N<<1];
long long ny[N<<1];
void init(){
ny[1]=1;
for(int i=2;i<=200000;i++)ny[i]=1ll*(mod-mod/i)*ny[mod%i]%mod;
not_prime[1]=1;
min_prime[1]=0;
for(int i=2;i<=200000;i++){
if(!not_prime[i])prime[++prime[0]]=i,min_prime[i]=i;
for(int j=1;j<=prime[0];j++){
if(i*prime[j]>200000)break;
int k=i*prime[j];
not_prime[k]=1;
min_prime[k]=prime[j];
if(i%prime[j]==0)break;
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
init();
for(int i=1;i<=n;i++){
root[i]=root[i-1];
while(min_prime[a[i]]){
int k=min_prime[a[i]],t=1;
while(a[i]%k==0){
t*=k,a[i]/=k;
if(pos[t])root[i]=T.insert(root[i],1,n,pos[t],ny[k]);
pos[t]=i;
}
root[i]=T.insert(root[i],1,n,i,t);
}
}
scanf("%d",&Q);
for(int i=1;i<=Q;i++){
int s1=0,s2=0;
scanf("%d%d",&s1,&s2);
s1=(s1+ans)%n+1,s2=(s2+ans)%n+1;
if(s1>s2)swap(s1,s2);
ans=T.ask(root[s2],1,n,s1)%mod;
printf("%lld\n",ans);
}
return 0;
}
标签:总结,rt,专题,int,prime,pos,include,数据结构
From: https://www.cnblogs.com/hxqasd/p/16855999.html