【线段树+数论】奇数国

数论, 线段树

传送门：UOJ38

清华集训2014 Orz

思路：

经转化可得题意要求求一段区间乘积的欧拉函数值

由公式可得：

$$\phi(x)=x\times \prod_{p_i|x}\frac{p_i-1}{p_i}$$

所以需要维护乘积x和质因子有哪些

线段树维护乘积不多说

由于只可能出现前60个质因子，用0/1二进制位表示，压到long long里

合并用位运算

注意：

不要把定义域和值域搞错

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
#define mo 19961993
#define N 120000
LL n,op,x,y,xb,ans1,ans2,prime[301],inv[301],sum[N*4],factor[N*4];
void getprime(int x){
	for (int i=2;i<=x;i++){
		bool flag=1;
		for (int j=2;j<=sqrt(i);j++)
			if (i%j==0){flag=0; break;}
		if (flag) prime[++xb]=i;
	}
}
void getinv(int x){
	inv[1]=1;
	for (int i=2;i<=x;i++) inv[i]=(mo-mo/i)*inv[mo%i]%mo;
}
void update(int cur){
	sum[cur]=sum[cur<<1]*sum[cur<<1|1]%mo;
	factor[cur]=factor[cur<<1]|factor[cur<<1|1];
}
void change(int cur,int l,int r,int x,int y){
	if (l==r){
		sum[cur]=y; factor[cur]=0;
		for (int i=1;i<=60;i++)
			if (y%prime[i]==0) factor[cur]|=(LL)1<<(i-1);
		return;
	}
	int mid=(l+r)>>1;
	if (x<=mid) change(cur<<1,l,mid,x,y);
	if (x>mid) change(cur<<1|1,mid+1,r,x,y);
	update(cur);
}
void query(int cur,int l,int r,int L,int R){
	if (L<=l && R>=r){
		ans1=ans1*sum[cur]%mo; ans2|=factor[cur];
		return;
	}
	int mid=(l+r)>>1;
	if (L<=mid) query(cur<<1,l,mid,L,R);
	if (R>mid) query(cur<<1|1,mid+1,r,L,R);
}
int main(){
	getprime(300);
	getinv(300);
	for (int i=1;i<=100000;i++)	change(1,1,N,i,3);
	
	scanf("%lld",&n);
	for (int i=1;i<=n;i++){
		scanf("%lld%lld%lld",&op,&x,&y);
		if (op==0){
			ans1=1; ans2=0;
			query(1,1,N,x,y);
			for (int i=1;i<=60;i++)
				if ((LL)1<<(i-1)&ans2){
					ans1=ans1*(prime[i]-1)%mo;
					ans1=ans1*inv[prime[i]]%mo;
				}
			printf("%lld\n",ans1);
		}
		if (op==1) change(1,1,N,x,y);
	}
	return 0;
}