首页 > 代码库 > 【bzoj4026】dC Loves Number Theory 可持久化线段树
【bzoj4026】dC Loves Number Theory 可持久化线段树
题目描述
输入
第一行，两个正整数，N，Q，表示序列的长度和询问的个数。
输出
Q行，对于每个询问输出一个整数。
样例输入
5 10
3 7 10 10 5
3 4
42 44
241 242
14 9
1201 1201
0 6
245 245
7 7
6 1
1203 1203
样例输出
40
240
12
1200
2
240
4
4
1200
4
题解
可持久化线段树（个人觉得不应该叫做主席树，因为本题是区间线段树）
前置技能：HH的项链 强制在线
标准的做法是离线+树状数组，但是由于要在线处理，所以只能尽量使用可持久化数据结构。
我们还是按照那道题的思路，对于每个数，当它出现时就把它上一次出现的位置删除掉。
那么我们就可以使用可持久化区间线段树完成这样类似的操作。
对于每个数a[i]，记录一下它上一个出现的位置last，在i对应的线段树中，把last位置的数-1，并把i位置的数+1。
这样在查询区间[l,r]的时候，在r对应的线段树中，查询[l,r]（[l,n]同理）这段区间内数的和即为答案。
比较复杂，稍微理解一下~
就当是理解完了
回过头来看这道题，要求区间乘积的欧拉函数。
欧拉函数是什么请自行百度，怎么求请自行找博客。
这里还是简单说一下吧，$\varphi(x)=x\sum\limits_{prime(i)\& i|x}\frac{i-1}i$。
所以说对于这道题可以维护一个前缀乘积，然后只需要求出区间内的质因子即可。
使用类似于HH的项链的方法，对于一个位置i，枚举a[i]的质因子，如果它在之前last位置出现过，则将i位置对应的线段树的last位置的数除以$\frac{i-1}i$；在i位置的数乘以$\fraci-1{i}$。
然后使用可持久化线段树维护区间乘积，查询[l,r]时求出r对应的线段树中[l,r]（[l,n]同理）的乘积，再乘上$\frac{mul[r]}{mul[l-1]}$（前缀积）即为答案。
需要筛逆元什么的，参见代码。
#include <cstdio>#include <algorithm>#define N 100010#define M 2100000using namespace std;typedef long long ll;const ll mod = 1000777 , k = 1000005;ll a[N] , prime[M] , cnt , last[M] , ls[N * 80] , rs[N * 80] , tot , root[N] , inv[M] , sum[N * 80] , mul[N];bool np[M];void update(ll p , ll v , ll l , ll r , ll x , ll &y){ y = ++tot , sum[y] = sum[x] * v % mod; if(l == r) return; ll mid = (l + r) >> 1; if(p <= mid) rs[y] = rs[x] , update(p , v , l , mid , ls[x] , ls[y]); else ls[y] = ls[x] , update(p , v , mid + 1 , r , rs[x] , rs[y]);}ll query(ll p , ll l , ll r , ll x){ if(l >= p) return sum[x]; if(r < p) return 1; ll mid = (l + r) >> 1; return query(p , l , mid , ls[x]) * query(p , mid + 1 , r , rs[x]) % mod;}int main(){ ll n , m , i , j , x , y; ll lastans = 0; scanf("%lld%lld" , &n , &m); for(i = 2 ; i <= k ; i ++ ) { if(!np[i]) prime[++cnt] = i; for(j = 1 ; j <= cnt && i * prime[j] <= k ; j ++ ) { np[i * prime[j]] = 1; if(i % prime[j] == 0) break; } } mul[0] = sum[0] = inv[1] = 1; for(i = 2 ; i < mod ; i ++ ) inv[i] = (mod - mod / i) * inv[mod % i] % mod; for(i = 1 ; i <= n ; i ++ ) { scanf("%lld" , &a[i]) , mul[i] = mul[i - 1] * a[i] % mod , root[i] = root[i - 1]; for(j = 1 ; prime[j] * prime[j] <= a[i] ; j ++ ) { if(a[i] % prime[j] == 0) { if(!last[prime[j]]) update(i , (prime[j] - 1) * inv[prime[j]] % mod , 1 , n , root[i] , root[i]); else update(last[prime[j]] , prime[j] * inv[prime[j] - 1] % mod , 1 , n , root[i] , root[i]) , update(i , (prime[j] - 1) * inv[prime[j]] % mod , 1 , n , root[i] , root[i]); last[prime[j]] = i; while(a[i] % prime[j] == 0) a[i] /= prime[j]; } } if(a[i] > 1) { if(!last[a[i]]) update(i , (a[i] - 1) * inv[a[i]] % mod , 1 , n , root[i] , root[i]); else update(last[a[i]] , a[i] * inv[a[i] - 1] % mod , 1 , n , root[i] , root[i]) , update(i , (a[i] - 1) * inv[a[i]] % mod , 1 , n , root[i] , root[i]); last[a[i]] = i; } } while(m -- ) scanf("%lld%lld" , &x , &y) , x ^= lastans , y ^= lastans , printf("%lld\n" , lastans = query(x , 1 , n , root[y]) * mul[y] % mod * inv[mul[x - 1]] % mod); return 0;}
【bzoj4026】dC Loves Number Theory 可持久化线段树