Description
Rikka and Yuta are interested in Phi function (which is known as Euler’s totient function). Yuta gives Rikka an array A[1..n] of positive integers, then Yuta makes m queries. There are three types of queries: 1 l r Change A[i] into φ(A[i]), for all i∈[l,r]. 2 l r x Change A[i] into x, for all i∈[l,r]. 3 l r Sum up A[i], for all i∈[l,r]. Help Rikka by computing the results of queries of type 3.
The first line contains a number
T(T≤100)
——The number of the testcases. And there are no more than 2 testcases with
n>105
For each testcase, the first line contains two numbers n,m(
n≤3∗105,m≤3∗105
)。 The second line contains n numbers A[i] .Each of the next m lines contains the description of the query.It is guaranteed that
1≤A[i]≤107
At any moment.
Output
For each query of type 3, print one number which represents the answer.
1
10 10
56 90 33 70 91 69 41 22 77 45
1 3 9
1 1 10
3 3 8
2 5 6 74
1 1 8
3 1 9
1 2 10
1 4 9
2 8 8 69
3 3 9
Sample Output
80
122
86
I think
题意： 1)一般线段树的加和操作 2)将节点值x改为
φ(x)
算法：线性筛欧拉函数+线段树 实现：作为一只第一次用到欧拉函数的蒟蒻，默默去膜了大佬们的筛法讲解，安利：几种常用的数学算法 线性筛欧拉函数 最后筛欧拉函数的代码就是这样啦
void Euler() {
memset(isp,
1,
sizeof(isp));
p[
0]=
0,isp[
1]=
0,phi[
1]=
1;
for(
int i=
2;i<sm;++i) {
if(isp[i]) p[++p[
0]]=i,phi[i]=i-
1;
for(
int j=
1;j<=p[
0]&&i*p[j]<=sm;++j) {
isp[i*p[j]]=
0;
if(i%p[j]==
0) { phi[i*p[j]]=phi[i]*p[j];
break;}
phi[i*p[j]]=phi[i]*(p[j]-
1);
}
}
}
而我们知道，对于一个数n反复取欧拉函数，它可以在
log(n)
的时间内最终变为1，如果有连着一大段一大段的1不是我们喜闻乐见的吗？——就可以把它们合作一个区间更新啦，因此在执行操作1时，更新需要满足的条件不再仅是ll<=l&&r<=rr，还需要再设一个标记表示是否整个区间均为1，同时满足k[i]==1即可，否则继续递归到满足要求为止。
Code
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const LL sm =
1e7+
10;
const LL mx =
1200000+
50;
LL n,m,T;
LL v,s[mx],k[mx];
int isp[sm],phi[sm],p[
700000];
char ch;
template <
typename T>
void read(T &x) {
x=
0,ch=getchar();
while(ch>
'9'||ch<
'0') ch=getchar();
while(ch>=
'0'&&ch<=
'9') x=x*
10+ch-
'0',ch=getchar();
}
void Euler() {
memset(isp,
1,
sizeof(isp));
p[
0]=
0,isp[
1]=
0,phi[
1]=
1;
for(
int i=
2;i<sm;++i) {
if(isp[i]) {
p[++p[
0]]=i;
phi[i]=i-
1;
}
for(
int j=
1;j<=p[
0]&&i*p[j]<=sm;++j) {
isp[i*p[j]]=
0;
if(i%p[j]==
0) {
phi[i*p[j]]=phi[i]*p[j];
break;
}
phi[i*p[j]]=phi[i]*(p[j]-
1);
}
}
}
void pushup(LL i,LL l,LL r) {
LL ls=i<<
1,rs=i<<
1|
1;
s[i]=s[ls]+s[rs];
if(k[ls]==k[rs]) k[i]=k[ls];
else k[i]=
0;
}
void pushdown(LL i,LL l,LL r) {
LL m=(l+r)>>
1,ls=i<<
1,rs=i<<
1|
1;
k[ls]=k[rs]=k[i];
s[ls]=(m-l+
1)*k[ls];
s[rs]=(r-m)*k[rs];
}
void build(LL i,LL l,LL r) {
s[i]=k[i]=
0;
if(l==r) {
read(v),s[i]=k[i]=v;
return;
}
LL m=(l+r)>>
1;
build(i<<
1,l,m);
build(i<<
1|
1,m+
1,r);
pushup(i,l,r);
}
void modify(LL i,LL l,LL r,LL ll,LL rr,LL val) {
if(ll<=l&&r<=rr) {
s[i]=(r-l+
1)*val,k[i]=val;
return ;
}
if(k[i])pushdown(i,l,r);
LL m=(l+r)>>
1;
if(ll<=m) modify(i<<
1,l,m,ll,rr,val);
if(rr> m) modify(i<<
1|
1,m+
1,r,ll,rr,val);
pushup(i,l,r);
}
void euler(LL i,LL l,LL r,LL ll,LL rr) {
if(k[i]&&ll<=l&&r<=rr) {
k[i]=phi[k[i]],s[i]=
1ll*k[i]*(r-l+
1);
return;
}
if(l==r)
return;
if(k[i]) pushdown(i,l,r);
LL m=(l+r)>>
1;
if(ll<=m) euler(i<<
1,l,m,ll,rr);
if(rr> m) euler(i<<
1|
1,m+
1,r,ll,rr);
pushup(i,l,r);
}
LL query(LL i,LL l,LL r,LL ll,LL rr) {
if(l>r)
return 0;
if(ll<=l&&r<=rr)
return s[i];
if(k[i]) pushdown(i,l,r);
LL m=(l+r)>>
1;
LL ans=
0;
if(ll<=m) ans+=query(i<<
1,l,m,ll,rr);
if(rr> m) ans+=query(i<<
1|
1,m+
1,r,ll,rr);
pushup(i,l,r);
return ans;
}
int main() {
Euler();
read(T);
LL ind,ll,rr,val;
while(T--) {
read(n),read(m);
build(
1,
1,n);
for(LL i=
1;i<=m;++i) {
read(ind),read(ll),read(rr);
if(ind==
2) read(val),modify(
1,
1,n,ll,rr,val);
else if(ind==
1) euler(
1,
1,n,ll,rr);
else printf(
"%lld\n",query(
1,
1,n,ll,rr));
}
}
return 0;
}
