【BZOJ4026】dC Loves Number Theory
Description
dC 在秒了BZOJ 上所有的数论题后，感觉萌萌哒，想出了这么一道水题，来拯救日益枯竭的水题资源。
给定一个长度为 n的正整数序列A，有q次询问，每次询问一段区间内所有元素乘积的φ（φ(n)代表1~n 中与n互质的数的个数） 。由于答案可能很大，所以请对答案 mod 10^6 + 777。 （本题强制在线，所有询问操作的l,r都需要 xor上一次询问的答案 lastans，初始时，lastans = 0）
Input
第一行，两个正整数，N，Q，表示序列的长度和询问的个数。
第二行有N 个正整数，第i个表示Ai.
下面Q行，每行两个正整数，l r，表示询问[l ^ lastans,r ^ lastans]内所有元素乘积的φ
Output
Q行，对于每个询问输出一个整数。
Sample Input
5 10 3 7 10 10 5 3 4 42 44 241 242 14 9 1201 1201 0 6 245 245 7 7 6 1 1203 1203
Sample Output
40 240 12 1200 2 240 4 4 1200 4
题解：前置技能：强制在线版HH的项链。（好吧这道题不存在的~）
用主席树实现强制在线求区间中不同数的个数，具体做法跟树状数组的做法差不多。比如当位置i的数是x，x上一个出现的位置是j，那么我们就在i的主席树中的位置j减去1（j本身的主席树不动！！！）。当我们查询区间[l,r]中，在r的主席树中进行区间查询，这样，如果r==i并且l>j，那么我们只计算了i的贡献；如果r==i并且l<=j，那么我们依旧没有计算j的贡献；如果r<i并且l<j，那么在i之前的主席树中并没有将j删去，我们还能正常计算j的贡献。（需要好好理解一下。）
然后就水了嘛！我们知道如果$n=\prod p_i^{e_i}(p是质数)$，那么$\varphi( n)=n\prod {p_i-1\over p_i}$，所以我们只需要先预处理出所有质数，然后将每个数分解质因数，维护区间中每个质数出现的次数就好了。具体做法是：当我们分解第i个位置上的数时，如果i包含e个质因子p，那么我们要找到p上一个出现的位置j，在i的主席树中将位置j乘上$p\over p-1$（因为j处之前肯定乘过p-1），然后在i的位置乘上$（p-1）*p^{e-1}$就行了。
需要用快速幂求逆元。
#include#include #include using namespace std;typedef long long ll;const int maxn=50010;const ll mod=1000777;int n,m,nm,num,ans,tot;int pri[100010],last[100010],np[1000010],v[maxn],rt[maxn];struct sag{ int ls,rs; ll sc;}s[maxn*160];ll pm(ll x,ll y){ ll z=1; while(y) { if(y&1) z=z*x%mod; x=x*x%mod,y>>=1; } return z;}int rd(){ int ret=0,f=1; char gc=getchar(); while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar(); return ret*f;}void insert(int x,int &y,int l,int r,int pos,int val){ if(l>r) return ; if(!y||y==x) y=++tot,s[y].sc=s[x].sc*val%mod; else s[y].sc=s[y].sc*val%mod; if(l==r) return ; int mid=l+r>>1; if(pos<=mid) s[y].rs=(s[y].rs)?s[y].rs:s[x].rs,insert(s[x].ls,s[y].ls,l,mid,pos,val); else s[y].ls=(s[y].ls)?s[y].ls:s[x].ls,insert(s[x].rs,s[y].rs,mid+1,r,pos,val);}ll query(int x,int l,int r,int a,int b){ if(a<=l&&r<=b) return s[x].sc; int mid=l+r>>1; if(b<=mid) return query(s[x].ls,l,mid,a,b); if(a>mid) return query(s[x].rs,mid+1,r,a,b); return query(s[x].ls,l,mid,a,b)*query(s[x].rs,mid+1,r,a,b)%mod;}int main(){ n=rd(),m=rd(); int i,j,a,b; for(i=1;i<=n;i++) v[i]=rd(),nm=max(nm,v[i]); for(i=2;i<=nm;i++) { if(!np[i]) np[i]=++num,pri[num]=i; for(j=1;j<=num&&i*pri[j]<=nm;j++) { np[i*pri[j]]=-1; if(i%pri[j]==0) break; } } s[0].sc=1; for(i=1;i<=n;i++) { if(v[i]==1) { insert(rt[i-1],rt[i],1,n,i,1); continue; } for(j=1;j<=num&&pri[j]*pri[j]<=v[i];j++) { if(v[i]%pri[j]==0) { v[i]/=pri[j],insert(rt[i-1],rt[i],1,n,i,pri[j]-1); while(v[i]%pri[j]==0) v[i]/=pri[j],insert(rt[i-1],rt[i],1,n,i,pri[j]); if(last[j]) insert(rt[i-1],rt[i],1,n,last[j],pm(pri[j]-1,mod-2)*pri[j]%mod); last[j]=i; } } if(v[i]>1) { j=np[v[i]]; if(last[j]) insert(rt[i-1],rt[i],1,n,last[j],pm(pri[j]-1,mod-2)*pri[j]%mod); last[j]=i,insert(rt[i-1],rt[i],1,n,i,pri[j]-1); } } for(i=1;i<=m;i++) { a=rd()^ans,b=rd()^ans; ans=int(query(rt[b],1,n,a,b)); printf("%d\n",ans); } return 0;}