「FCS NOI 2018 day1」欧拉函数 - 线段树+bitset+欧拉函数 | Bill Yang's Blog
0%

「FCS NOI 2018 day1」欧拉函数 - 线段树+bitset+欧拉函数

题目大意

    对于正整数$n$,定义欧拉函数$\varphi(n)$为小于等于$n$且与$n$互质的正整数个数。例如$\varphi(1)=1,\varphi(8)=4$。
    给定正整数序列$a_1,a_2,\ldots,a_n$,请依次执行$q$个操作,操作有以下三种类型:

  • $\underline{0 \ i \ x}$:修改$a_i$的值为$x$。
  • $\underline{1 \ l \ r}$:查询$\varphi(a_l+a_{l+1}+\cdots+a_r)$的值,输出其对$10^9+7$取模后的结果。
  • $\underline{2 \ l \ r}$:查询$\varphi(a_l\times a_{l+1}\times\cdots\times a_r)$的值,输出其对$10^9+7$取模后的结果。
        数据随机。

题目分析

本做法不是标解,标解使用树状数组/分治来维护欧拉函数的质因数分解。
本做法有些卡常,考试时仅得到$85$分。

有了奇数国的基础,不难想到对欧拉函数质因数分解,用bitset维护每个质因数是否出现过。
分析一下时间复杂度。
$40000$内有$4203$个素数,故若只考虑$0,2$操作时间复杂度为$O(n\sqrt{40000}+q\log n\cdot4203)$
这个复杂度明显有问题,若我们使用bitset自带的遍历$1$元素的函数即可做到$O(n\sqrt{40000}+q\log n\cdot\min(\frac{4203}{64},1\text{的个数}))$,由于数据随机性,复杂度勉强可以接受。
现在考虑$1$操作,由于求和后欧拉函数不满足任何性质,故只能暴力求解,可以预处理出部分欧拉函数,对$a_i$求和后查询欧拉函数(若在预处理范围内直接输出,否则暴力计算),由于数据的随机性,故时间效率并不低下(实际上不预处理欧拉函数都快的飞起)。

根据常数的大小,分数在$90\sim100$间徘徊。


代码

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include<cstdio>
#include<bitset>
#include<cmath>

namespace FastIO {
const int L=1<<15;
char buffer[L],*S,*T;
inline char getchar() {
if(S==T) {T=(S=buffer)+fread(buffer,1,L,stdin);if(S==T)return EOF;}
return *S++;
}
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
inline void Put_Int(int x) {
if(x<0)putchar('-'),x=-x;
if(x>9)Put_Int(x/10);
putchar(x%10+'0');
}
}

using namespace FastIO;

const int maxn=50005,maxm=20005,maxq=100005,maxv=45005,maxi=4205,mod=1e9+7;

int vst[maxv],pr[maxv],id[maxv],cnt=0,mul[maxi];
int a[maxn];
bool bj=0;
std::bitset<maxi> pre[maxn+maxm];

void Prime_Table(int n) {
for(int i=2; i<=n; i++) {
if(!vst[i])pr[++cnt]=i;
for(int j=1; j<=cnt&&i*pr[j]<=n; j++) {
vst[i*pr[j]]=1;
if(i%pr[j]==0)break;
}
}
}

struct Tree {
int left,right;
int sum,mul;
std::bitset<maxi> vst;
Tree(int l=0,int r=0):left(l),right(r),sum(0),mul(1) {}
Tree operator + (const Tree &b) const {
Tree c=*this;
c.right=b.right;
c.sum+=b.sum;
if(bj) {
c.mul=1ll*c.mul*b.mul%mod;
c.vst|=b.vst;
}
return c;
}
} tree[maxn<<2];

struct Segment_Tree {
#define ls index<<1
#define rs index<<1|1
void build(int index,int Left,int Right) {
tree[index]=Tree(Left,Right);
if(Left==Right) {
tree[index].sum=tree[index].mul=a[Left];
if(bj)tree[index].vst=pre[Left];
return;
}
int mid=(Left+Right)>>1;
build(ls,Left,mid);
build(rs,mid+1,Right);
push_up(index);
}
void push_up(int index) {tree[index]=tree[ls]+tree[rs];}
void modify(int index,int tar,int cnt,int val) {
if(tree[index].left==tree[index].right) {
tree[index].sum=tree[index].mul=val;
if(bj)tree[index].vst=pre[cnt];
return;
}
int mid=(tree[index].left+tree[index].right)/2;
if(tar<=mid)modify(ls,tar,cnt,val);
else modify(rs,tar,cnt,val);
push_up(index);
}
Tree query(int index,int Left,int Right) {
if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index];
if(Left>tree[ls].right)return query(rs,Left,Right);
if(Right<tree[rs].left)return query(ls,Left,Right);
return query(ls,Left,Right)+query(rs,Left,Right);
}
} st;

int n,q,idx=0,tot=0,inv[maxi],tmp[maxn+maxm];

struct Query {
int opt,x,y;
} Q[maxq];

int Phi(int x) {
int ans=x;
for(int i=1; i<=cnt&&sqrt(x)>=pr[i]; i++)
if(x%pr[i]==0) {
while(x%pr[i]==0)x/=pr[i];
ans-=ans/pr[i];
}
if(x>1)ans-=ans/x;
return ans;
}

int Quick_Pow(int a,int b) {
int ans=1;
for(; b; b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;
return ans;
}

int main() {
Prime_Table(45000);
n=Get_Int();
q=Get_Int();
for(int i=1; i<=n; i++)tmp[++tot]=a[i]=Get_Int();
for(int i=1; i<=q; i++) {
Q[i].opt=Get_Int();
Q[i].x=Get_Int();
Q[i].y=Get_Int();
if(Q[i].opt==0)tmp[++tot]=Q[i].y;
if(Q[i].opt==2)bj=1;
}
if(bj) {
for(int i=1; i<=tot; i++) {
int x=tmp[i];
for(int j=1; j<=cnt&&sqrt(x)>=pr[j]; j++)
if(x%pr[j]==0) {
while(x%pr[j]==0)x/=pr[j];
if(!id[pr[j]])id[pr[j]]=++idx,mul[idx]=1ll*Quick_Pow(pr[j],mod-2)*(pr[j]-1)%mod;
pre[i].flip(id[pr[j]]);
}
if(x>1) {
if(!id[x])id[x]=++idx,mul[idx]=1ll*Quick_Pow(x,mod-2)*(x-1)%mod;
pre[i].flip(id[x]);
}
}
}
st.build(1,1,n);
tot=n;
for(int i=1; i<=q; i++) {
if(Q[i].opt==0)st.modify(1,Q[i].x,++tot,Q[i].y);
else {
Tree x=st.query(1,Q[i].x,Q[i].y);
if(Q[i].opt==1) {Put_Int(Phi(x.sum));putchar('\n');}
else {
int ans=x.mul,tmp=x.vst.count();
for(int i=x.vst._Find_first(); tmp; i=x.vst._Find_next(i))ans=1ll*ans*mul[i]%mod,tmp--;
Put_Int(ans);putchar('\n');
}
}
}
return 0;
}
姥爷们赏瓶冰阔落吧~