\(\text{Solution}\)

首先把 \(T2\) 给切了，\(T1\) 找半天规律找不到

然后打了个表算是暴力了

\(T3\) 也暴。。。

太暴了。。。

\(T4\) 直接啥也不会

\(\text{T1}\)

考虑一个 \(a\) 的答案

\((c+b)(c-b)=a^2\) 或 \((c+b)(c-b)=(a+1)(a-1)\) 的 \(c,b\) 组数

就是一般的分类讨论了，记一个数 \(a\) 的答案为 \(f(a)\)，\(d(a)\) 为 \(a\) 的约数个数

那么 \(2\nmid a,f(a)=d(a)/2\)

\(4\mid a,f(a)=d(a/4)/2\)

其余则为 \(0\)

具体考虑 \(a^2\) 和 \(a^2-1\) 的 \(f\) 值即可

\(\text{Code}\)

#include <cstdio>

#define RE register

using namespace std;

typedef long long LL;

const int N = 1e7 + 5;

int x, y, d[N], _d[N], num[N], tot, pr[N / 10], vis[N], ans;

void Sieve()

{

	d[1] = _d[1] = num[1] = 1;

	for(RE int i = 2; i <= 1e7 + 3; i++)

	{

		if (!vis[i]) pr[++tot] = i, d[i] = 2, num[i] = 1, _d[i] = 3;

		for(RE int j = 1, z; j <= tot && pr[j] * i <= 1e7 + 3; j++)

		{

			vis[z = i * pr[j]] = 1;

			if (i % pr[j] == 0)

			{

				num[z] = num[i] + 1, d[z] = d[i] / num[z] * (num[z] + 1);

				_d[z] = _d[i] / (num[i] * 2 + 1) * (num[z] * 2 + 1);

				break;

			}

			else d[z] = d[i] * 2, num[z] = 1, _d[z] = _d[i] * 3;

		}

	}

}

int main()

{

	Sieve(), scanf("%d%d", &x, &y);

	for(RE int a = x; a <= y; a++)

		if (a & 1) ans += (LL)_d[a] / 2 + (LL)d[(a + 1) / 2] * d[(a - 1) / 2] / 2;

		else ans += (LL)d[a + 1] * d[a - 1] / 2 + _d[a / 2] / 2;

	printf("%d\n", ans);

}

\(\text{T2}\)

一眼分位变成线段树赋值和异或操作

\(\text{Code}\)

#include <cstdio>

#define RE register

#define IN inline

using namespace std;

const int N = 5e4 + 5, LG = 9, SZ = N * 4, M = LG + 2;

int n, m, a[N];

struct SegmenTree{

	#define ls (p << 1)

	#define rs (ls | 1)

	int sum[SZ][M], tg1[SZ][M], tg2[SZ][M];

	IN void pushup(int p, int k){sum[p][k] = sum[ls][k] + sum[rs][k];}

	void build(int p, int l, int r)

	{

		for(RE int j = 0; j <= LG; j++) tg1[p][j] = -1;

		if (l == r)

		{

			for(RE int j = 0; j <= LG; j++) sum[p][j] = ((a[l] >> j) & 1);

			return;

		}

		int mid = l + r >> 1; build(ls, l, mid), build(rs, mid + 1, r);

		for(RE int j = 0; j <= LG; j++) pushup(p, j);

	}

	IN void push(int p, int k, int z, int l, int r)

	{

		if (z == 0 || z == 1) sum[p][k] = z * (r - l + 1), tg1[p][k] = z;

		else{

			sum[p][k] = r - l + 1 - sum[p][k], tg2[p][k] ^= 1;

			if (tg1[p][k] != -1) tg1[p][k] ^= 1;

		}

	}

	IN void pushdown(int p, int k, int l, int r)

	{

		int mid = l + r >> 1;

		if (tg2[p][k]) push(ls, k, 2, l, mid), push(rs, k, 2, mid + 1, r), tg2[p][k] = 0;

		if (tg1[p][k] != -1) push(ls, k, tg1[p][k], l, mid), push(rs, k, tg1[p][k], mid + 1, r), tg1[p][k] = -1;

	}

	void assign(int p, int l, int r, int k, int x, int y, int z)

	{

		if (x > r || y < l) return;

		if (x <= l && r <= y) return push(p, k, z, l, r), void();

		pushdown(p, k, l, r); int mid = l + r >> 1;

		if (x <= mid) assign(ls, l, mid, k, x, y, z);

		if (y > mid) assign(rs, mid + 1, r, k, x, y, z);

		pushup(p, k);

	}

	void reverse(int p, int l, int r, int k, int x, int y)

	{

		if (x > r || y < l) return;

		if (x <= l && r <= y) return push(p, k, 2, l, r), void();

		pushdown(p, k, l, r); int mid = l + r >> 1;

		if (x <= mid) reverse(ls, l, mid, k, x, y);

		if (y > mid) reverse(rs, mid + 1, r, k, x, y);

		pushup(p, k);

	}

	int Query(int p, int l, int r, int k, int x, int y)

	{

		if (x > r || y < l) return 0;

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

		pushdown(p, k, l, r); int mid = l + r >> 1, res = 0;

		if (x <= mid) res = Query(ls, l, mid, k, x, y);

		if (y > mid) res += Query(rs, mid + 1, r, k, x, y);

		return res;

	}

}T;

int main()

{

	scanf("%d%d", &n, &m);

	for(RE int i = 1; i <= n; i++) scanf("%d", &a[i]);

	T.build(1, 1, n); char op[10];

	for(RE int l, r, x; m; --m)

	{

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

		if (op[0] == 'a'){

			scanf("%d", &x);

			for(RE int j = 0; j <= LG; j++) if (!((x >> j) & 1)) T.assign(1, 1, n, j, l, r, 0);

		}

		else if (op[0] == 'o'){

			scanf("%d", &x);

			for(RE int j = 0; j <= LG; j++) if ((x >> j) & 1) T.assign(1, 1, n, j, l, r, 1);

		}

		else if (op[0] == 'x'){

			scanf("%d", &x);

			for(RE int j = 0; j <= LG; j++) if ((x >> j) & 1) T.reverse(1, 1, n, j, l, r);

		}

		else if (op[1] == 'x'){

			int res = 0, z;

			for(RE int j = 0; j <= LG; j++) z = T.Query(1, 1, n, j, l, r), res += ((z & 1) ? (1 << j) : 0);

			printf("%d\n", res);

		}

		else{

			int res = 0, z;

			for(RE int j = 0; j <= LG; j++) z = T.Query(1, 1, n, j, l, r), res += z * (1 << j);

			printf("%d\n", res);

		}

	}

}

巴特西

JZOJ 2022.02.11【提高A组】模拟

\(\text{Solution}\)

\(\text{T1}\)

\(\text{Code}\)

\(\text{T2}\)

\(\text{Code}\)

最新文章

热门文章