Luogu P3934 [Ynoi2016]炸脖龙I 题解

考虑一下没有修改操作怎么做。

这里需要用到扩展欧拉定理:

    \[a^b=\left\{ \begin{aligned} a^b \ \ (b <\varphi(p)) \\ a^{b\ mod\ \varphi(p)+\varphi(p)}\ \ (b\ge \varphi(p)) \end{aligned} \right.(mod\ p)\]

(请把上面的等号自动看成同余号,因为我不会打同余号)

使用递归暴力求解a[l]~a[r]的所求值。一个数经过log次取欧拉函数都会变成1,因此每次查询复杂度O(log n)

考虑修改。由于查询只需要暴力查询单点值,因此需要一个数据结构支持区间加和单点查询。使用树状数组随意搞一搞。

戳我看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 500050;
const int MAXM = 20000050;
void read(int &x) {
	char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
	while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
int phi[MAXM], n, m, notp[MAXM], p[MAXM], cntp;
struct Data {int ans, flag;};
struct BITS {
	int t[MAXN];
	void update(int x, int val) {for(; x <= n; t[x] += val, x += x&-x);}
	void U(int l, int r, int val) {update(r+1, -val); update(l, val);}
	int Q(int x) {int res = 0; for(; x; res += t[x], x -= x&-x); return res;}
} T;
Data power(int a, int b, int p) {
	Data res = (Data) {1, 0};
	if(a >= p) res.flag = 1, a %= p;
	for(; b; b >>= 1) {
		if(b & 1) res.ans *= a;
		if(res.ans >= p) res.flag = 1, res.ans %= p;
		a *= a;
		if(a >= p) res.flag = 1, a %= p;
	}
	return res;
}
Data solve(int l, int r, int p) {
	int x = T.Q(l); Data res;
	if(p == 1) return (Data) {0, 1};
	if(x == 1) return (Data) {1, 0};
	if(l == r) return x < p ? (Data) {x, 0} : (Data) {x%p, 1};
	res = solve(l+1, r, phi[p]);
	if(res.flag) res.ans += phi[p];
	return power(x, res.ans, p);
}
void GetPhi() {
	phi[1] = 1;
	for(int i = 2; i <= 2e7; ++i) {
		if(!notp[i]) p[++cntp] = i, phi[i] = i-1;
		for(int j = 1; j <= cntp; ++j) {
			int t = i * p[j];
			if(t > 2e7) break;
			notp[t] = 1;
			if(i % p[j] == 0) {phi[t] = phi[i] * p[j]; break;}
			phi[t] = phi[i] * (p[j] - 1);
		}
	}
}
signed main() {
	GetPhi(); read(n); read(m);
	for(int x, i = 1; i <= n; ++i) read(x), T.U(i, i, x);
	for(int opt, l, r, x; m--; ) {
		read(opt); read(l); read(r); read(x);
		if(opt == 1) T.U(l, r, x);
		else printf("%d\n", solve(l, r, x).ans);
	}
}
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

正在获取,请稍候...
00:00/00:00