[文章目录]
Description
给定一个长度为 n的正整数序列A，有q次询问，每次询问一段区间内所有元素乘积的φ（φ(n)代表1~n 中与n互质的数的个数） 。由于答案可能很大，所以请对答案 mod 10^6+777。（本题强制在线，所有询问操作的l,r都需要 xor上一次询问的答案 lastans，初始时，lastans = 0） n<=5 * 10^4 q<=10^5 ai<=10^6
如果离线的话可以对于询问按照r排序，线段树维护区间出现的所有（质数-1）/质数的乘积，二分l。对于r移动，将a[r]分解质因数，在每个质因子的上一个位置删除该因子，当前r加入，只会有n * log(ai) 次修改 q * 次查询。
对于质数p关于模数的(p-1)/p，快筛mod以内的逆元即可。
在线的话，主席树可持久化一下就好了。时间复杂度O(n * log ai * log n +q * log n)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=1000777;
ll Pow(ll x)
{
ll re=1; int y=mod-2;
while(y)
{
if(y&1) re=re*x%mod;
x=x*x%mod; y>>=1;
}
return re;
}
int pri[701000],cnt,Inv[1001000],yz[1001000];
void initialize()
{
Inv[1]=1; yz[1]=1;
for(int i=2;i<=mod;++i)
{
if(!Inv[i]) pri[++cnt]=i,Inv[i]=Pow(i),yz[i]=i;
for(int j=1;i*pri[j]<=mod&&j<=cnt;++j)
{
yz[i*pri[j]]=pri[j];
Inv[i*pri[j]]=(ll)Inv[i]*Inv[pri[j]]%mod;
if(!(i%pri[j])) break;
}
}
}
struct seg
{
int ls,rs,w;
}t[17000000];
int n,m,rot[50100],now[1001000],s[50100];
int se;
void fix(int &x,int y,int l,int r,int z,int w)
{
x=++se; t[x].w=(ll)t[y].w*w%mod;
if(l==r) return ;
int mid=(l+r)>>1;
if(z<=mid) t[x].rs=t[y].rs,fix(t[x].ls,t[y].ls,l,mid,z,w);
else t[x].ls=t[y].ls,fix(t[x].rs,t[y].rs,mid+1,r,z,w);
}
int query(int pos,int l,int r,int z)
{
if(l==r) return t[pos].w;
int mid=(l+r)>>1;
if(z<=mid) return (ll)t[t[pos].rs].w*query(t[pos].ls,l,mid,z)%mod;
else return query(t[pos].rs,mid+1,r,z);
}
int main()
{
initialize();
scanf("%d%d",&n,&m);
int x,y; s[0]=1; t[0].w=1;
for(int i=1;i<=n;++i)
{
rot[i]=rot[i-1];
scanf("%d",&x); s[i]=(ll)s[i-1]*x%mod;
while(x!=1)
{
if(now[yz[x]])
{
fix(rot[i],rot[i],1,n,now[yz[x]],(ll)Inv[yz[x]-1]*yz[x]%mod);
}
fix(rot[i],rot[i],1,n,i,(ll)(yz[x]-1)*Inv[yz[x]]%mod);
now[yz[x]]=i; y=yz[x];
while(x%y==0) x/=y;
}
}
int l,r,ans=0;
while(m--)
{
scanf("%d%d",&l,&r); l^=ans; r^=ans;
ans=(ll)s[r]*Inv[s[l-1]]%mod*query(rot[r],1,n,l)%mod;
printf("%d\n",ans);
}
return 0;
}