「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$间徘徊。

---

代码

#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;
}