[uoj 38]【清华集训2014】奇数国

长度为10^5的正整数序列, 任意时刻质因子属于前60个素数且不超过10^6, 初始均为3. 要求支持: - 单点修改 - 查询区间积的欧拉函数模19961993

(操作次数不超过10^5) 同时是bzoj 3813, 但是题面不如uoj清爽. 打一个素数表. 19961993是质数, 所以也可以直接打表. 用线段树维护区间积取模, 取模之前所含质因子的集合 (一个长度为60的位向量即可).

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)

using namespace std;
typedef unsigned long long ull;
const int M = 60, N = 1e5, MOD = 19961993,
	prime[] = {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},
	d[] = {9980997,13307996,7984798,11406854,14517814,18426456,9393880,5253157,16490343,8260136,2575742,18343454,3895024,17640832,1698894,3013132,7443456,4581442,9236147,18275065,6562848,2779519,7936697,4037258,6379607,19566707,13566404,4104336,3662752,13602421,16661192,1219054,13259427,9047523,3751248,8196316,14621843,1714528,12192356,11884887,8029406,13455046,17976246,13342473,14084859,15548287,10217514,9846724,5364237,3486812,1627803,14950615,1076789,12406658,19340609,8652728,7791857,7955334,1657495,8808852};

ull prod[N * 4], fac[N * 4];

ull decompose(ull n)
{
	ull s = 0;
	Rep (i, 0, M)
		if (n % prime[i] == 0)
			s |= (1LL<<i);
	return s;
}

inline void up(int o)
{
	prod[o] = (prod[o*2] * prod[o*2+1]) % MOD;
	fac[o] = fac[o*2] | fac[o*2+1];
}

void build(int o, int l, int r)
{
	if (l == r) {
		fac[o] = 2;
		prod[o] = 3;
		return;
	}
	int m = (l+r)/2;
	build(o*2, l, m);
	build(o*2+1, m+1, r);
	up(o);
}

void modify(int o, int l, int r, int x, ull v, ull s)
{
	if (l == r) {
		fac[o] = s;
		prod[o] = v;
		return;
	}
	int m = (l+r)/2;
	if (x <= m) modify(o*2, l, m, x, v, s);
	else modify(o*2+1, m+1, r, x, v, s);
	up(o);
}

ull query(int o, int l, int r, int L, int R, ull& s)
{
	if (L <= l && r <= R) {
		s |= fac[o];
		return prod[o];
	}
	int m = (l+r)/2;
	ull p = 1;
	if (L <= m) p = query(o*2, l, m, L, R, s);
	if (R > m) (p *= query(o*2+1, m+1, r, L, R, s)) %= MOD;
	return p;
}

int main()
{
	build(1, 1, N);
	int q;
	scanf("%d", &q);
	while (q--) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		if (a) {
			ull t = decompose(c);
			modify(1, 1, N, b, c, t);
		} else {
			ull s = 0, t = query(1, 1, N, b, c, s);
			Rep (i, 0, M) {
				if (s & 1)
					(t *= d[i]) %= MOD;
				s >>= 1;
			}
			printf("%llu\n", t);
		}
	}
	return 0;
}