奇数国（线段树）
有一个长度为n的数列，开始时每一项值都为3，这个数列中每一项都为3。这个数列中每一项都只包含前60个质数的质因数。
有两种操作：1是修改数列中一项的值，保证值小于1e6。2是询问与一段区间【l，r】的积x互质并且小于x的数的个数，答案对1e9+7取模。n和m小于50万。
由于只有60个质数，线段树维护二进制60位即可。
#include <cstdio>
using namespace std;typedef long long LL;
const LL mod=19961993, maxn=1e5+5;
const LL p[61]={ 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 };
LL m, ie[300];LL bi[maxn*4], pro[maxn*4];LL bians, proans;
void query(LL x, LL l, LL r, LL L, LL R){if (l>=L&&r<=R){ bians|=bi[x]; proans=proans*pro[x]%mod; return; }LL mid=(l+r)>>1;if (mid>=L) query(x<<1, l, mid, L, R);if (mid<R) query(x<<1|1, mid+1, r, L, R);
}void modify(LL x, LL l, LL r, LL pos, LL v){if (l==r){pro[x]=v; bi[x]=0;for (LL i=1; i<61; ++i) if (v%p[i]==0) bi[x]|=(1ll<<i);return; }LL mid=(l+r)>>1;if (mid>=pos) modify(x<<1, l, mid, pos, v);else modify(x<<1|1, mid+1, r, pos, v);bi[x]=bi[x<<1]|bi[x<<1|1]; pro[x]=pro[x<<1]*pro[x<<1|1]%mod;
}int main(){ie[1]=1; for (LL i=2; i<300; ++i){ie[i]=-(mod/i)*ie[mod%i]%mod+mod; ie[i]%=mod; }scanf("%lld", &m); LL op, a1, a2, t, ans;for (LL i=1; i<maxn; ++i) modify(1, 1, maxn, i, 3);for (LL i=0; i<m; ++i){scanf("%lld%lld%lld", &op, &a1, &a2);if (!op){ans=proans=1; bians=0;query(1, 1, maxn, a1, a2); t=bians;for (LL i=1; i<61; ++i)if (t&(1LL<<i)) ans=ans*(p[i]-1)%mod*ie[p[i]]%mod;ans=ans*proans%mod;printf("%lld\n", ans);} else modify(1, 1, maxn, a1, a2);}return 0;
}