# HDU 5634 Rikka with Phi (线段树)

Problem Description

Rikka and Yuta are interested in Phi function (which is known as Euler's totient function). Yuta gives Rikka an array  of positive integers, then Yuta makes  queries.   There are three types of queries:  Change  into , for all . Change  into , for all . Sum up , for all . Help Rikka by computing the results of queries of type 3.

Input

The first line contains a number  ——The number of the testcases. And there are no more than 2 testcases with  For each testcase, the first line contains two numbers 。 The second line contains  numbers  Each of the next  lines contains the description of the query.  It is guaranteed that  At any moment.

Output

For each query of type 3, print one number which represents the answer.

Sample Input

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

#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
typedef long long int LL;
const int maxn=1e5;
bool check[maxn*100+5];
LL prime[maxn*100+5];
LL eul[maxn*100+5];
LL sum[maxn*20+5];
LL a[maxn*20+5];
int n,m;
/*void eular(){
eul[1] = 1;
for (int i = 2; i<maxn*100+5; i++) eul[i] = i;
for (int i = 2; i<maxn*100+5; i++)
if (eul[i] == i)
for (int j = i; j<maxn*100+5; j += i) eul[j] = eul[j] / i*(i - 1);
}
*/
void eular()
{
memset(check,false,sizeof(check));
eul[1]=1;
int tot=0;
for(int i=2;i<=maxn*100+5;i++)
{
if(!check[i])
{
prime[tot++]=i;
eul[i]=i-1;
}
for(int j=0;j<tot;j++)
{
if(i*prime[j]>maxn*100+5) break;
check[i*prime[j]]=true;
if(i%prime[j]==0)
{
eul[i*prime[j]]=eul[i]*prime[j];
break;
}
else
{
eul[i*prime[j]]=eul[i]*(prime[j]-1);
}

}
}
}

void pushup(int node)
{
sum[node]=sum[node<<1]+sum[node<<1|1];
if(a[node<<1]==a[node<<1|1])
a[node]=a[node<<1];
else
a[node]=0;
}
void pushdown(int node,int l,int r)
{
int mid=(l+r)>>1;
if(a[node])
{
sum[node<<1]=a[node]*(mid-l+1);
sum[node<<1|1]=a[node]*(r-mid);
a[node<<1]=a[node<<1|1]=a[node];
//c[node<<1]=c[node<<1|1]=c[node];
a[node]=0;
}
}
void build(int node,int l,int r)
{
if(l==r)
{
scanf("%lld",&a[node]);
sum[node]=a[node];
return ;
}
int mid=(l+r)>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
pushup(node);
}
void update1(int node,int l,int r,int L,int R,LL tag)
{
if(L<=l&&r<=R)
{
sum[node]=(LL)tag*(r-l+1);
a[node]=tag;
//c[node]=tag;
return;
}
if(a[node]) pushdown(node,l,r);
int mid=(l+r)>>1;
if(L<=mid)
update1(node<<1,l,mid,L,R,tag);
if(R>mid)
update1(node<<1|1,mid+1,r,L,R,tag);
pushup(node);
}
void update2(int node,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
if(a[node])
{
a[node]=eul[a[node]];
sum[node]=a[node]*(r-l+1);
return;
}

int mid=(l+r)>>1;
if(L<=mid)
update2(node<<1,l,mid,L,R);
if(R>mid)
update2(node<<1|1,mid+1,r,L,R);
pushup(node);
return ;
}
if(a[node]) pushdown(node,l,r);
int mid=(l+r)>>1;
if(L<=mid)
update2(node<<1,l,mid,L,R);
if(R>mid)
update2(node<<1|1,mid+1,r,L,R);
pushup(node);
}
LL query(int node,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
return sum[node];
}
if(a[node]) pushdown(node,l,r);

int mid=(l+r)>>1;
LL ret=0;
if(L<=mid)
ret+=query(node<<1,l,mid,L,R);
if(R>mid)
ret+=query(node<<1|1,mid+1,r,L,R);

return ret;
}
int main()
{
int t;
scanf("%d",&t);
int x,y,z;
LL w;
eular();
while(t--)
{
scanf("%d%d",&n,&m);
build(1,1,n);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
if(x==1)
{
update2(1,1,n,y,z);
}
else if(x==2)
{
scanf("%lld",&w);
update1(1,1,n,y,z,w);
}
else
{
printf("%lld\n",query(1,1,n,y,z));
}
}
}
return 0;
}

0 条评论

## 相关文章

1943

2858

### Go语言中new和make的区别

Go语言中new和make是内建的两个函数，主要用来创建分配类型内存。在我们定义生成变量的时候，可能会觉得有点迷惑，其实他们的规则很简单，下面我们就通过一些示例...

1222

### UAF Writeup - pwnable.kr

0x00 UAF — pwnable.kr是一个韩国的CTF练习的网站，有很多经典的CTF题目供爱好者练习。 UAF(Use After Free)释放后重用...

3686

### Python黑帽编程2.4 流程控制

Python黑帽编程2.4 流程控制 本节要介绍的是Python编程中和流程控制有关的关键字和相关内容。 2.4.1 IF …..ELSE 先上一段代码： ...

2844

### 理解Java8的数据类型和运行时数据区域

Java虚拟机包含对对象的显式支持，对象要么是动态分配的类实例，要么是静态数组，对对象的引用我们可以叫做指针或者引用，一个对象可以有多个引用，对象总是通过引用的...

1523

2063

### C++中的作用域与生命周期

Pascal之父Nicklaus Wirth曾经提出一个公式，展示出了程序的本质：程序=算法+数据结构。后人又给出一个公式与之遥相呼应：软件=程序+文档。这两个...

802

3548

5426