2017-07-06

【清华集训2014】奇数国

本文为博主原创，未经许可不得转载

AC通道

果然提交人数多的题都是水题

显然答案是$\phi(product)$，也就是求区间积的欧拉函数并支持修改操作

只需要用线段树记录区间积的质因子分解就行了

#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 100100
#define N 100000
using namespace std;
typedef long long ll;
const int mod=19961993;
int Q,tot,ans[65],cnt[65],prime[65],check[305],tr[MAXN<<2][65];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline int sub(int a,int b){return (a-=b)<0?a+mod:a;}
inline int mul(int a,int b){return 1LL*a*b%mod;}
inline int fast(int a,int b){int ret(1);for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
void relord(int p){
	for(int i=1;i<=60;++i)
		tr[p][i]=tr[p<<1][i]+tr[p<<1|1][i];
}
void build(int p,int l,int r){
	if(l==r){
		tr[p][2]++;
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);  build(p<<1|1,mid+1,r);
	relord(p);
}
void updata(int p,int l,int r,int x){
	if(l==r){
		for(int i=1;i<=60;++i)tr[p][i]=cnt[i];
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) updata(p<<1,l,mid,x);
	else       updata(p<<1|1,mid+1,r,x);
	relord(p);
}
void query(int p,int l,int r,int x,int y){
	if(x<=l&&y>=r){
		for(int i=1;i<=60;++i)
			ans[i]+=tr[p][i];
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) query(p<<1,l,mid,x,y);
	if(y>mid)  query(p<<1|1,mid+1,r,x,y);
}
void solve(int n){
	for(int i=1;i<=60;++i)while(n%prime[i]==0)
		cnt[i]++,n/=prime[i];
}
void output(){
	ll ret=1;
	for(int i=1;i<=60;++i)if(ans[i])
		ret=mul(ret,mul(prime[i]-1,fast(prime[i],ans[i]-1)));
	printf("%lld\n",ret);
}
void pre(){
	for(int i=2;i<=281;++i){
		if(!check[i]) prime[++tot]=i;
		for(int j=1;j<=tot&&prime[j]*i<=281;++j){
			check[prime[j]*i]=1;
			if(i%prime[j]==0) break;
		}
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	Q=read(); pre(); build(1,1,N);
	for(int i=1;i<=Q;++i){
		int opt=read();
		if(opt==0){
			int l=read(),r=read();
			memset(ans,0,sizeof(ans));
			query(1,1,N,l,r);
			output();
		}
		else{
			int x=read(),v=read();
			memset(cnt,0,sizeof(cnt));
			solve(v);
			updata(1,1,N,x);
		}
	}
	return 0;
}

本文标题:【清华集训2014】奇数国

文章作者:chty

发布时间:2017年07月06日 - 20时41分

最后更新:2018年06月08日 - 18时45分

许可协议:本文为博主原创，未经许可不得转载。