【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 <cstdio>

#include <cstring>

#include <iostream>

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;

}

巴特西

【BZOJ4026】dC Loves Number Theory 分解质因数+主席树