如果mod是质数就好做了，但是做除法的时候对于合数mod可能没有逆元。所以就只有存一下mod的每个质因数(最多9个)的幂，和剩下一坨与mod互质的一部分。然后就能做了。有点恶心。
CODE

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 100005;

const int MAXP = 9;

int n, q, a[MAXN], p[MAXP], cnt, mod, phi;

inline int qpow(int a, int b) {

	int re=1;

	for(;b;a=1ll*a*a%mod,b>>=1)if(b&1)re=1ll*re*a%mod;

	return re;

}

struct node {

	int ind[MAXP];

	node () { memset(ind, 0, sizeof ind); }

	inline int init(int x) {

		memset(ind, 0, sizeof ind);

		for(int i = 0; i < cnt; ++i)

			while(x % p[i] == 0)

				x /= p[i], ind[i]++;

		return x;

	}

	inline void operator *=(const node &o) {

		for(int i = 0; i < cnt; ++i)

			ind[i] += o.ind[i];

	}

	inline void operator /=(const node &o) {

		for(int i = 0; i < cnt; ++i)

			ind[i] -= o.ind[i];

	}

	inline int calc() {

		int re = 1;

		for(int i = 0; i < cnt; ++i)

			re = 1ll * re * qpow(p[i], ind[i]) % mod;

		return re;

	}

}tag[MAXN<<2]; //tag存mod的质因数的幂

int res[MAXN<<2], rlz[MAXN<<2]; //res存与mod互质的部分的积

int sum[MAXN<<2], lz[MAXN<<2]; //sum存答案

inline void pre(int x) {

	phi = x;

	for(int i = 2; i*i <= x; ++i)

		if(x % i == 0) {

			p[cnt++] = i, phi = phi / i * (i-1);

			while(x % i == 0) x /= i;

		}

	if(x > 1) p[cnt++] = x, phi = phi / x * (x-1);

}

inline void upd(int i) { sum[i] = (sum[i<<1] + sum[i<<1|1]) % mod; }

inline void pd(int i) {

	tag[i<<1] *= tag[i], tag[i<<1|1] *= tag[i];

	memset(tag[i].ind, 0, sizeof tag[i].ind);

	if(lz[i] != 1) {

		sum[i<<1] = 1ll * sum[i<<1] * lz[i] % mod;

		lz[i<<1] = 1ll * lz[i<<1] * lz[i] % mod;

		sum[i<<1|1] = 1ll * sum[i<<1|1] * lz[i] % mod;

		lz[i<<1|1] = 1ll * lz[i<<1|1] * lz[i] % mod;

		lz[i] = 1;

	}

	if(rlz[i] != 1) {

		res[i<<1] = 1ll * res[i<<1] * rlz[i] % mod;

		rlz[i<<1] = 1ll * rlz[i<<1] * rlz[i] % mod;

		res[i<<1|1] = 1ll * res[i<<1|1] * rlz[i] % mod;

		rlz[i<<1|1] = 1ll * rlz[i<<1|1] * rlz[i] % mod;

		rlz[i] = 1;

	}

}

void build(int i, int l, int r) {

	//printf("SSS (%d,%d,%d)\n", i, l, r);

	lz[i] = rlz[i] = 1;

	if(l == r) {

		int x; scanf("%d", &x);

		res[i] = tag[i].init(x) % mod;

		sum[i] = x % mod;

		return;

	}

	int mid = (l + r) >> 1;

	build(i<<1, l, mid);

	build(i<<1|1, mid+1, r);

	upd(i);

}

void multi(int i, int l, int r, int x, int y, int num, node v, int val) {

	if(x <= l && r <= y) {

		tag[i] *= v;

		lz[i] = 1ll * lz[i] * val % mod;

		sum[i] = 1ll * sum[i] * val % mod;

		rlz[i] = 1ll * rlz[i] * num % mod;

		res[i] = 1ll * res[i] * num % mod;

		return;

	}

	pd(i);

	int mid = (l + r) >> 1;

	if(x <= mid) multi(i<<1, l, mid, x, y, num, v, val);

	if(y > mid) multi(i<<1|1, mid+1, r, x, y, num, v, val);

	upd(i);

}

void divide(int i, int l, int r, int x, int num, node v) {

	if(l == r) {

		sum[i] = res[i] = 1ll * res[i] * qpow(num, phi-1) % mod;

		tag[i] /= v; sum[i] = 1ll * sum[i] * tag[i].calc() % mod;

		return;

	}

	pd(i);

	int mid = (l + r) >> 1;

	if(x <= mid) divide(i<<1, l, mid, x, num, v);

	else divide(i<<1|1, mid+1, r, x, num, v);

	upd(i);

}

inline int query(int i, int l, int r, int x, int y) {

	if(x <= l && r <= y) return sum[i];

	int mid = (l + r) >> 1, re = 0; pd(i);

	if(x <= mid) re = (re + query(i<<1, l, mid, x, y)) % mod;

	if(mid < y) re = (re + query(i<<1|1, mid+1, r, x, y)) % mod;

	return re;

}

int main() {

	scanf("%d%d", &n, &mod); pre(mod);

	build(1, 1, n);

	scanf("%d", &q);

	int op, l, r, x;

	int num; node tmp;

	while(q--) {

		scanf("%d", &op);

		if(op == 1) {

			scanf("%d%d%d", &l, &r, &x);

			num = tmp.init(x);

			multi(1, 1, n, l, r, num, tmp, x);

		}

		else if(op == 2) {

			scanf("%d%d", &l, &x);

			num = tmp.init(x);

			divide(1, 1, n, l, num, tmp);

		}

		else {

			scanf("%d%d", &l, &r);

			printf("%d\n", query(1, 1, n, l, r));

		}

	}

}
巴特西

Codeforces Round #539 (Div. 1) E - Sasha and a Very Easy Test 线段树

CODE

最新文章

热门文章
