dC Loves Number Theory

题目大意：dC 在秒了BZOJ 上所有的数论题后，感觉萌萌哒，想出了这么一道水题，来拯救日益枯竭的水题资源。给定一个长度为 n的正整数序列A，有q次询问，每次询问一段区间内所有元素乘积的φ（φ(n)代表1~n 中与n互质的数的个数）。由于答案可能很大，所以请对答案 mod 10^6 + 777。（本题强制在线，所有询问操作的l,r都需要 xor上一次询问的答案 lastans，初始时，lastans = 0）

数据范围：1<=N<=50000，1<=Q<=100000，1<=Ai<=10^6。

题解：

完全不会.....

听了$lijinnn$讲了才明白。

有一个非常非常重要的性质，如果没发现的话根本做不了。

我们考虑暴力怎么搞：每次全扫一遍，然后统计答案。

这也太暴力了....我们优化优化。

这样，每个位置开一个长度最多为$7$的数组表示当前位置的质因子因为我们知道：

$\varphi(n) = n*\prod\limits_{p_i|n} \frac{p_i - 1}{p_i}$。

这复杂度是$O(n^2\times 7)$的。

再优化优化？？？

发现，对于每个左端点，我可以维护处每个质因子在当前左端点右边最靠左出现的位置。

就是先扫一遍整个数组，先求出来左端点在$1$时，每个质数最左出现的位置。

接着每次，左端点往右动，更新当前左端点所在位置的值的所有质因子的答案即可，这样再查询就是在左端点对应的数组上查就好了，这是$O(n)$的。

好，现在的复杂度到了$O(n^2)$，重点就是维护每个质因子在不超过左端点的情况下，最左的位置。

那正解不就出来了么！

我们发现，左端点每动一次，更改的值只有最多$7$个，剩下的值都是相同的。

什么东西可以维护这个？就是一大堆都一样，只有几个不同

主席树呀，我们对每个左端点开一棵主席树，直接维护刚才说的数组。

咋维护呢？

就是对于第$i$颗主席树，如果有一个质数$p$在$i$左侧最左的位置是$j$，那就在主席树$j$的位置$*=\frac{p - 1}{p}$，然后主席树节点维护所支配区间所有数乘积。

但是，每个点单独质因数分解是$O(n\sqrt{a_i})$的，我们通过预处理质数，然后枚举质数的方式就好啦，复杂度是调和级数$O(nln\ n)$。

主席树的复杂度是$O(nlogn)$，每次$O(loglogn)$次，总复杂度是$O(nlognloglogn + nln\ n)$。

代码：

#include <bits/stdc++.h>

#define N 50010 

using namespace std;

const int mod = 1000777 ;

typedef long long ll;

vector <int> v[1000010 ];

int prime[1000010 ], cnt;

bool vis[1000010 ];

int pre[1000010 ], bfr[N], a[N];

int ls[N * 200], rs[N * 200], sum[N * 200], root[N * 200], tot;

char *p1, *p2, buf[100000];

#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

int rd() {

	int x = 0, f = 1;

	char c = nc();

	while (c < 48) {

		if (c == '-')

			f = -1;

		c = nc();

	}

	while (c > 47) {

		x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();

	}

	return x * f;

}

int qpow(int x, int y) {

	int ans = 1;

	while (y) {

		if (y & 1)

			ans = (ll)ans * x % mod;

		y >>= 1;

		x = (ll)x * x % mod;

	}

	return ans;

}

void init() {

	for (int i = 2; i <= 1000000; i ++ ) {

		if (!vis[i])

			prime[ ++ cnt] = i;

		for (int j = 1; j <= cnt && (ll)i * prime[j] <= 1000000; j ++ ) {

			vis[i * prime[j]] = true;

			if (i % prime[j] == 0) {

				break;

			}

		}

	}

}

void update(int x, int val, int l, int r, int pre, int &p) {

	p = ++tot;

	ls[p] = ls[pre];

	rs[p] = rs[pre];

	sum[p] = (ll)sum[pre] * val % mod;

	if (l == r) {

		return;

	}

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

	if (x <= mid)

		update(x, val, l, mid, ls[pre], ls[p]);

	else

		update(x, val, mid + 1, r, rs[pre], rs[p]);

}

int query(int x, int y, int l, int r, int p) {

	if (!p) {

		return 1;

	}

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

		return sum[p];

	}

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

	if (x <= mid)

		ans = (ll)ans * query(x, y, l, mid, ls[p]) % mod;

	if (mid < y)

		ans = (ll)ans * query(x, y, mid + 1, r, rs[p]) % mod;

	return ans;

}

int main() {

	int n = rd(), m = rd();

	for (int i = 1; i <= n; i ++ ) {

		a[i] = rd();

	}

	bfr[0] = 1;

	for (int i = 1; i <= n; i ++ ) {

		bfr[i] = (ll)bfr[i - 1] * a[i] % mod;

	}

	init();

	for (int i = 1; i <= cnt; i ++ ) {

		for (int j = prime[i]; j <= 1000000; j += prime[i]) {

			v[j].push_back(i);

		}

	}

	// cout << prime[cnt] << endl ;

	// for (int i = 1; i <= n; i ++ ) {

	// 	int len = v[a[i]].size();

	// 	for (int j = 0; j < len; j ++ ) {

	// 		printf("%d ",prime[v[a[i]][j]]);

	// 	}

	// 	puts("");

	// }

	sum[0] = 1;

	for (int i = 1; i <= n; i ++ ) {

		int len = v[a[i]].size();

		for (int j = 0; j < len; j ++ ) {

			if (pre[v[a[i]][j]]) {

				update(pre[v[a[i]][j]], (ll)prime[v[a[i]][j]] * qpow(prime[v[a[i]][j]] - 1, mod - 2) % mod, 1, n, (root[i] ? root[i] : root[i - 1]), root[i]);

			}

			update(i, (ll)(prime[v[a[i]][j]] - 1) * qpow(prime[v[a[i]][j]], mod - 2) % mod, 1, n, (root[i] ? root[i] : root[i - 1]), root[i]);

			// printf("Shit %d\n",v[a[i]][j]);

			pre[v[a[i]][j]] = i;

		}

	}

	// cout << sum[root[1]] << endl ;

	// cout << (ll)sum[root[1]] * 3 % mod * qpow(2, mod - 2) % mod << endl ;

	// cout << sum[root[4]] << endl ;

	// cout << (ll)sum[root[4]] * 2 * 6 * 4 % mod * qpow(3, mod - 2) % mod * qpow(2, mod - 2) % mod * qpow(5, mod - 2) % mod * qpow(7, mod - 2) % mod << endl ;

	// puts("Fuck");

	int lastans = 0;

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

		int x = rd(), y = rd();

		x ^= lastans, y ^= lastans;

		if (x > y) {

			lastans = 1;

			puts("0");

			continue;

		}

		// cout << (ll)bfr[y] * qpow(bfr[x - 1], mod - 2) % mod << endl ;

		lastans = (ll)bfr[y] * qpow(bfr[x - 1], mod - 2) % mod * query(x, y, 1, n, root[y]) % mod;

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

	}

	return 0;

}

小结：真的是好题啊，重要的是那个性质能不能发现。主席树的运用也非常巧妙。

巴特西

[bzoj4026]dC Loves Number Theory_主席树_质因数分解_欧拉函数

dC Loves Number Theory

最新文章

热门文章