题目大意：给出一段长度为$100000$的初始值为$3$的序列。有两种操作：1.把$a_x$的值改为$y$；2.求$varphi (prod _{i=l}^r a_i)mod 19961993$的值。
-----------------------------------
题目比较显然，可以用线段树维护区间积。
欧拉函数的通式：$varphi (n)=n*(1-frac{p_1-1}{p_1})*(1-frac{p_2-1}{p_2})*cdots *(1-frac{p_k-1}{p_k}),n=p_1^{c_1}*p_2^{c_2}*cdots *p_k^{c_k}$。
根据题意，我们可以打表出质数表和逆元表。
线段树维护一个$tag$，用来压位$sum$的质因子。需要的时候直接位运算统计答案即可。
时间复杂度$O(q(60+log n))$。
PS:考试的时候我怎么这么傻逼，没写逆元模数直接GG。数据结构也写的一坨屎……
代码：
#include<bits/stdc++.h> #define int long long using namespace std; const int mod=19961993; int prime[65]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281}; int inv[65]={0,9980997,6653998,11977196,8555140,5444180,1535538,10568114,14708837,3471651,11701858,17386252,1618540,16066970,2321162,18263100,16948862,12518538,15380552,10725847,1686929,13399146,17182475,12025297,15924736,13582387,395287,6395590,15857658,16299242,6359573,3300802,18742940,6702567,10914471,16210746,11765678,5340151,18247466,7769638,8077107,11932588,6506948,1985748,6619521,5877135,4413707,9744480,10115270,14597757,16475182,18334191,5011379,18885205,7555336,621385,11309266,12170137,12006660,18304499,11153142}; int q; struct node { int index,l,r,sum,tag; }tree[500005]; inline int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void pushup(int index) { tree[index].sum=tree[index*2].sum*tree[index*2+1].sum%mod; tree[index].tag=tree[index*2].tag|tree[index*2+1].tag; } inline void build(int index,int l,int r) { tree[index].l=l; tree[index].r=r; if (l==r) { tree[index].sum=3; tree[index].tag=2; return; } int mid=(l+r)>>1; build(index*2,l,mid); build(index*2+1,mid+1,r); pushup(index); } inline void update(int index,int pos,int x) { if (tree[index].l==tree[index].r) { tree[index].sum=x; tree[index].tag=0; for (int i=1;i<=60;i++) if (!(x%prime[i])) tree[index].tag|=1ll<<(i-1); return; } int mid=(tree[index].l+tree[index].r)>>1; if (pos<=mid) update(index*2,pos,x); else update(index*2+1,pos,x); pushup(index); } inline pair<int,int> query(int index,int l,int r) { if (l<=tree[index].l&&tree[index].r<=r) return make_pair(tree[index].sum,tree[index].tag); int mid=(tree[index].l+tree[index].r)>>1;pair<int,int> res;res.first=1;res.second=0; if (l<=mid) { pair<int,int> sum=query(index*2,l,r); res.first=res.first*sum.first%mod; res.second|=sum.second; } if (r>mid) { pair<int,int> sum=query(index*2+1,l,r); res.first=res.first*sum.first%mod; res.second|=sum.second; } return res; } inline int calc(int x,int tag) { int ans=x; for (int i=1;i<=60;i++) if (tag&(1ll<<(i-1))) ans=ans*inv[i]%mod*(prime[i]-1)%mod; return ans; } signed main() { q=read(); build(1,1,100000); for (int i=1;i<=q;i++) { int opt=read(),l=read(),r=read(); if (opt==1) update(1,l,r); else{ pair<int,int> ans=query(1,l,r); printf("%lld ",calc(ans.first,ans.second)); } } return 0; }