题意：
给定一个初始均为3的长度为100000的序列，有m个操作，分为以下两种：
⒈0 x y 设a[x~y]的区间积为sum，求[1~sum]中与sum互质的数的个数
⒉1 x y 将a[x]变为y
数据保证a[i]<=1000000，且a[i]的唯一分解为的素数为最小的前60个素数(p1=2,p2=3,…,p60=281)
题解：
①求区间乘积的欧拉函数取模
②√n求欧拉函数的方法
③用两棵线段树，一棵维护乘积，一棵维护质因数（状态压缩，压成一个LL）
④预处理乘法逆元和素数
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int maxn=100000+10,Mod=19961993,Inf=2e9; const int n=100000; struct Tree{ int left,right; LL val; }a[2][maxn<<2]; LL Bit[65]; LL Prime[305],cnt,Inv[305]; bool vis[305]; void Prework(); void Insert(int,int,int); void Build(int,int,int,int); void Pushup(int,int); void Update(int,int,int,int); LL Query(int,int,int,int); LL Pow(LL,LL); void Query(int,int); void Change(int,int,int,int); int main(){ Prework(); Build(0,1,1,n);//线段树0维护区间乘积 Build(1,1,1,n);//线段树1维护质因数的选择情况 int t;scanf("%d",&t); int op,x,y; while(t--){ scanf("%d%d%d",&op,&x,&y); if(op==0)Query(x,y); else Update(0,1,x,y),Update(1,1,x,y); } return 0; } void Prework(){ Inv[1]=1; for(int i=2;i<=300;i++){ Inv[i]=Pow(i,Mod-2); if(!vis[i])Prime[++cnt]=i; for(int j=1;i*j<=300;j++) vis[i*j]=1; } Bit[0]=1; for(int i=1;i<=60;i++) Bit[i]=Bit[i-1]<<1; } LL Pow(LL x,LL p){ LL ans=1; while(p){ if(p&1)ans=ans*x%Mod; x=x*x%Mod; p>>=1; } return ans; } void Insert(int op,int u,int val){ if(op==0)a[op][u].val=val; else{ a[op][u].val=0; for(int i=1;i<=60;i++) if(val%Prime[i]==0)//当前val包含质数Prime[i] a[op][u].val+=Bit[i-1]; } } void Pushup(int op,int u){ if(op==0)a[op][u].val=a[op][u<<1].val*a[op][u<<1|1].val%Mod; else a[op][u].val=a[op][u<<1].val|a[op][u<<1|1].val; } void Build(int op,int u,int left,int right){ a[op][u].left=left;a[op][u].right=right; if(left==right){ Insert(op,u,3);return; } int mid=(left+right)>>1; Build(op,u<<1,left,mid); Build(op,u<<1|1,mid+1,right); Pushup(op,u); } LL Query(int op,int u,int left,int right){ if(left==a[op][u].left && right==a[op][u].right)return a[op][u].val; int mid=(a[op][u].left+a[op][u].right)>>1; if(right<=mid)return Query(op,u<<1,left,right);//询问区间完全在左子树上 else if(left>mid)return Query(op,u<<1|1,left,right);//询问区间完全在右子树上 else{//询问区间在两子树上 if(op==0)return Query(op,u<<1,left,mid)*Query(op,u<<1|1,mid+1,right)%Mod; else return Query(op,u<<1,left,mid)|Query(op,u<<1|1,mid+1,right); } } void Query(int left,int right){ LL tmp1=Query(0,1,left,right); LL tmp2=Query(1,1,left,right); for(int i=1;i<=60;i++) if(tmp2&Bit[i-1]) tmp1=tmp1*(Prime[i]-1)%Mod*Inv[Prime[i]]%Mod; printf("%lld ",tmp1); } void Update(int op,int u,int x,int val){ if(a[op][u].left==a[op][u].right){ Insert(op,u,val);return; } int mid=(a[op][u].left+a[op][u].right)>>1; if(x<=mid)Update(op,u<<1,x,val); else Update(op,u<<1|1,x,val); Pushup(op,u); }
