非常神奇地都死在了小数据上（？？？）

提交记录

代码

#include<bits/stdc++.h>
using namespace std;
#define mod 19961993
#define N 100000
#define l(x) x*2
#define r(x) x*2+1
#define mid (l+r)/2
#define o(x) a[x].o
#define sum(x) a[x].sum
struct seg{
	long long o,sum;
}a[N*8];
const long long p[60]={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};
const long long ip[60]={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 n;
void build(int x,int l,int r)
{
	if(l==r){o(x)=2;sum(x)=3;return;}
	build(l(x),l,mid);
	build(r(x),mid+1,r);
	sum(x)=sum(l(x))*sum(r(x))%mod;
}
void insert(int x,int l,int r,int pos,int o,int num)
{
	if(l==r){o(x)=o;sum(x)=num;return;}
	if(pos<=mid) insert(l(x),l,mid,pos,o,num);
	else insert(r(x),mid+1,r,pos,o,num);
	o(x)=o(l(x))|o(r(x));
	sum(x)=sum(l(x))*sum(r(x))%mod;
	//cout<<x<<' '<<l<<' '<<r<<' '<<o(x)<<' '<<sum(x)<<endl;
}
seg query(int x,int l,int r,int L,int R)
{
	if(l==L&&r==R)return a[x];
	seg z,y;
	z.o=0;z.sum=1;
	if(R<=mid)return query(l(x),l,mid,L,R);
	else if(L>mid)return query(r(x),mid+1,r,L,R);
	else
	{
		y=query(l(x),l,mid,L,mid);
		z.o|=y.o;
		z.sum=z.sum*y.sum%mod;
		y=query(r(x),mid+1,r,mid+1,R);
		z.o|=y.o;
		z.sum=z.sum*y.sum%mod;
	}
	return z;
}
int main()
{
	build(1,1,N);
	long long u,x,y,z;
	seg v;
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x>>y>>z;
		if(x)
		{
			x=0;
			for(int j=0;j<60;j++)x|=(1ll<<j)*(z%p[j]==0);
			//cout<<bitset<sizeof(long long)*8>(x)<<'\n';
			insert(1,1,N,y,x,z);
		}
		else
		{
			v=query(1,1,N,y,z);
			x=v.sum;
			//cout<<x<<' '<<bitset<sizeof(long long)*8>(v.o)<<' '<<v.o<<' ';
			for(int j=0;j<60;j++)if(v.o&(1ll<<j))x=x*(p[j]-1)%mod*ip[j]%mod;
			cout<<x<<'\n';
		}
	}
}