欧拉函数+线段树
因为只有60个素数，所以把状态压成long long的形式。用线段树维护区间和和区间和中有多少个质数。然后xjb搞搞就行了，具体参见代码。
//BZOJ 3813//by Cydiater//2016.10.10#include <iostream>#include <cstdlib>#include <cstdio>#include <cmath>#include <queue>#include <map>#include <ctime>#include <cstring>#include <string>#include <algorithm>#include <iomanip>using namespace std;#define ll long long#define up(i,j,n)for(ll i=j;i<=n;i++)#define down(i,j,n)for(ll i=j;i>=n;i--)const ll MAXN=1e6+5;const ll oo=1LL<<60;const ll mod=19961993;const ll LIM=1e6;const ll N=1e5;inline ll read(){char ch=getchar();ll x=0,f=1;while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}ll inv[MAXN],prime[MAXN],cnt=0,T,x,y,k,v;struct Tree{ll S,v;}t[MAXN<<2];bool vis[MAXN];namespace solution{void exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return;}exgcd(b,a%b,x,y);ll t=x;x=y;y=t-a/b*y;}ll get_inv(ll a,ll b){ll x,y;exgcd(a,b,x,y);while(x<0)x+=b;return x;}ll get_suf(ll S){ll ans=1;up(i,0,59)if((1LL<<i)&S)ans=(ans*(prime[i+1]-1)%mod*inv[i+1]%mod)%mod;return ans;}ll get_two(ll num){ll S=0;up(i,1,60)if(num%prime[i]==0)S|=(1LL<<(i-1));return S;}Tree merge(Tree x,Tree y){x.S|=y.S;(x.v*=y.v)%=mod;return x;}void pret(){memset(vis,0,sizeof(vis));up(i,2,LIM){if(!vis[i])prime[++cnt]=i;up(j,1,cnt){if(prime[j]*i>LIM)break;vis[i*prime[j]]=1;if(i%prime[j]==0)break;}}up(i,1,60)inv[i]=get_inv(prime[i],mod);}void build(int leftt,int rightt,int root){if(leftt==rightt){t[root].S=1<<1;t[root].v=3;return;}int mid=(leftt+rightt)>>1;build(leftt,mid,root<<1);build(mid+1,rightt,root<<1|1);t[root].S=t[root<<1].S|t[root<<1|1].S;t[root].v=t[root<<1].v*t[root<<1|1].v%mod;}Tree get(int leftt,int rightt,int root){if(leftt>y||rightt<x)return (Tree){0,1};if(leftt>=x&&rightt<=y)return t[root];int mid=(leftt+rightt)>>1;Tree tmp=merge(get(leftt,mid,root<<1),get(mid+1,rightt,root<<1|1));return tmp;}void updata(int leftt,int rightt,int root){if(leftt>k||rightt<k)return;if(leftt==rightt){t[root].v=v;t[root].S=get_two(v);return;}int mid=(leftt+rightt)>>1;updata(leftt,mid,root<<1);updata(mid+1,rightt,root<<1|1);t[root]=merge(t[root<<1],t[root<<1|1]);}void slove(){T=read();while(T--){ll a=read(),b=read(),c=read();if(a==0){x=b;y=c;Tree tmp=get(1,N,1);printf("%lld\n",tmp.v*get_suf(tmp.S)%mod);}else{k=b;v=c;updata(1,N,1);}}}}int main(){//freopen("input.in","r",stdin);using namespace solution;pret();build(1,N,1);slove();return 0;}
