Luogu4433：[COCI2009-2010#1] ALADIN(类欧几里德算法)

先套用一个线段树维护离散化之后的区间的每一段的答案

那么只要考虑怎么下面的东西即可

\[\sum_{i=1}^{n}(A\times i \ mod \ B)
\]

拆开就是

\[\sum_{i=1}^{n}A\times i-B\times \sum_{i=1}^{n}\lfloor\frac{A\times i}{B}\rfloor
\]

只要考虑计算 \(\sum_{i=1}^{n}\lfloor\frac{A\times i}{B}\rfloor\) 即可

类欧几里德算法

若 \(A>B\)，那么就是

\[\lfloor\frac{A}{B}\rfloor\sum_{i=1}^{n}i+\sum_{i=1}^{n}\lfloor\frac{(A \ mod \ B)\times i}{B}\rfloor
\]

变成 \(A<B\) 的情况

对于 \(A<B\)，那么可以看成是求直线 \(y=\frac{A}{B}\times i,i\in[1,n]\) 与坐标轴围成的三角形中的整点的个数

设 \(m=\lfloor\frac{A\times n}{B}\rfloor\)

把问题为矩形 \((0,0),(n,m)\) 内的减去三角形 \((0,0),(n,m),(0,m)\) 内的再加上对角线的

对角线上的就是 \(\frac{n\times gcd(A,B)}{B}\)，矩形内的就是 \(n\times m\)

对于那个三角形的，反转坐标系后相当于是求直线 \(y=\frac{B}{A}\times i,i\in[1,\lfloor\frac{A\times n}{B}\rfloor]\) 与坐标轴围成的三角形中的整点的个数

即

\[\sum_{i=1}^{\lfloor\frac{A\times n}{B}\rfloor}\lfloor\frac{B\times i}{A}\rfloor
\]

递归处理即可，复杂度和 \(gcd\) 一样

可以先把 \(A,B\) 同时除去 \(gcd\) 后再做

这个题注意一个细节

\[\sum_{i=1}^{n}A\times i-B\times \sum_{i=1}^{n}\lfloor\frac{A\times i}{B}\rfloor
\]

直接求的可能会爆 \(long \ long\)

可以对 \(B\) 分段，算出长度为 \(B\) 的乘上 \(\lfloor\frac{n}{B}\rfloor\)，再加上长度为 \(n \ mod \ B\) 的，可以接受

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace IO {

	const int maxn(1 << 21 | 1);

	char ibuf[maxn], *iS, *iT, c;

	int f;

	inline char Getc() {

		return iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++)) : *iS++;

	}

	template <class Int> inline void In(Int &x) {

		for (f = 1, c = Getc(); c < '0' || c > '9'; c = Getc()) f = c == '-' ? -1 : 1;

		for (x = 0; c >= '0' && c <= '9'; c = Getc()) x = (x << 1) + (x << 3) + (c ^ 48);

		x *= f;

	}

}

using IO :: In;

const int maxn(1e5 + 5);

int n, m, o[maxn], cnt;

struct Segment {

	ll sum;

	int a, b, l;

} tr[maxn << 2];

inline void Update(int x) {

	tr[x].sum = tr[x << 1].sum + tr[x << 1 | 1].sum;

}

inline int Gcd(int a, int b) {

	return !b ? a : Gcd(b, a % b);

}

inline ll Mul(int a, int b, int len) {

	register int k = a / b;

	register ll sum = 1LL * k * (len + 1) * len / 2;

	if (!(a %= b) || !b) return sum;

	register int m = 1LL * len * a / b;

	assert(m >= 0);

	return 1LL * len * m + len / b - Mul(b, a, m) + sum;

}

inline ll Calc(int a, int b, int len) {

	if (len < 1 || a == b || b == 1) return 0;

	register int g = Gcd(a, b);

	return 1LL * a * len * (len + 1) / 2 - 1LL * b * Mul(a / g, b / g, len);

}

inline ll Solve(int a, int b, int len) {

	register ll ret = Calc(a, b, len % b);

	if (len >= b) ret += 1LL * len / b * Calc(a, b, b);

	return ret;

}

inline void Add(int x, int a, int b, int l, int len) {

	tr[x].a = a, tr[x].b = b, tr[x].l = l;

	tr[x].sum = Solve(a, b, l + len - 1) - Solve(a, b, l - 1);

}

inline void Pushdown(int x, int l, int r) {

	if (!tr[x].a) return;

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

	Add(x << 1, tr[x].a, tr[x].b, tr[x].l, o[mid] - o[l]);

	Add(x << 1 | 1, tr[x].a, tr[x].b, tr[x].l + o[mid] - o[l], o[r] - o[mid]);

	tr[x].a = tr[x].b = tr[x].l = 0;

}

ll Query(int x, int l, int r, int ql, int qr) {

	if (l >= qr || r <= ql) return 0;

	if (ql <= l && qr >= r) return tr[x].sum;

	Pushdown(x, l, r);

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

	register ll ret = 0;

	if (ql <= mid) ret = Query(x << 1, l, mid, ql, qr);

	if (qr >= mid) ret += Query(x << 1 | 1, mid, r, ql, qr);

	return ret;

}

void Modify(int x, int l, int r, int ql, int qr, int a, int b) {

	if (l >= qr || r <= ql) return;

	if (ql <= l && qr >= r) {

		Add(x, a, b, o[l] - o[ql] + 1, o[r] - o[l]);

		return;

	}

	Pushdown(x, l, r);

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

	if (ql <= mid) Modify(x << 1, l, mid, ql, qr, a, b);

	if (qr >= mid) Modify(x << 1 | 1, mid, r, ql, qr, a, b);

	Update(x);

}

int op[maxn], ql[maxn], qr[maxn], a[maxn], b[maxn];

int main () {

	In(n), In(m);

	register int i, l, r;

	for (i = 1; i <= m; ++i) {

		In(op[i]), In(ql[i]), In(qr[i]), --ql[i];

		o[++cnt] = ql[i], o[++cnt] = qr[i];

		if (op[i] == 1) In(a[i]), In(b[i]);

	}

	sort(o + 1, o + cnt + 1), cnt = unique(o + 1, o + cnt + 1) - o - 1;

	for (i = 1; i <= m; ++i) {

		l = lower_bound(o + 1, o + cnt + 1, ql[i]) - o;

		r = lower_bound(o + 1, o + cnt + 1, qr[i]) - o;

		if (op[i] == 1) Modify(1, 1, cnt, l, r, a[i], b[i]);

		else printf("%lld\n", Query(1, 1, cnt, l, r));

	}

	return 0;

}

巴特西

Luogu4433：[COCI2009-2010#1] ALADIN(类欧几里德算法)

最新文章

热门文章