题解[六省联考 2017] 相逢是问候

题目描述

Informatik verbindet dich und mich.
信息将你我连结。

B 君希望以维护一个长度为 \(n\) 的数组,这个数组的下标为从 \(1\) 到 \(n\) 的正整数。

一共有 \(m\) 个操作,可以分为两种:

$0 $ \(l\) \(r\) :表示将第 \(l\) 个到第 \(r\) 个数中的每一个数 \(a_i\) 替换为 \(c^{a_i}\)。

\(1\) \(l\) \(r\) :求第 \(l\) 个到第 \(r\) 个数的和。

Sol

难写又难调的数学题

若能相逢,无需问候。

一些知识点:

1.欧拉函数
2.快速幂
3.线段树

原理别的巨佬已经讲得特别好了,这里主要说一说代码实现。

首先:每一次模数都会变为他自己的欧拉函数,而且这个变换的次数是有限的。

所以一旦模数变成\(1​\) ,我们就可以再也不管它了!(怎么有点残忍

接着:快速幂要提前处理好,但是\(p\)有\(10^8\) ,我们要把这个值域分成两块,查询的时候求积。

还有:线段树查询区间和,暴力修改单点(最多\(nlogn\)次)。

看代码。

预处理部分

\(pow1[i]:c^i\)

\(pow2[i]:c^{10000i}\)

inline void oula(){
	ll tmp=P;
	phi[0]=P;
	while(tmp>1) tmp=Phi(tmp),phi[++mn]=tmp;//处理出所有要用的phi
	phi[++mn]=1;
  //phi[i]:对P取phi i次得到的值
  //pow1[i]:c^i
  //pow2[i]:c^{10000*i}
	for(int i=0;i<=mn;i++){
		pow1[i][0]=1;
		for(int j=1;j<=10000;j++){
			pow1[i][j]=pow1[i][j-1]*c;
			if(pow1[i][j]>=phi[i]) f1[i][j]=1,pow1[i][j]%=phi[i];//超过就打标记
			f1[i][j]|=f1[i][j-1];//一旦有一个超过,后面的必然超过
		}3
	}
	for(int i=0;i<=mn;i++){
		pow2[i][0]=1;
		for(int j=1;j<=10000;j++){
			pow2[i][j]=pow2[i][j-1]*pow1[i][10000];
			if(pow2[i][j]>=phi[i]) f2[i][j]=1,pow2[i][j]%=phi[i];
			f2[i][j]|=f2[i][j-1];
		}
	}
	return;
}

快速幂

记得打标记!!!

乘了就要判。

inline ll ksm(ll a,ll b){
	ll v1=b%10000,v2=b/10000;
  //分成两段
	flag|=f1[a][v1]|f2[a][v2];//打标记
	ll res=pow1[a][v1]*pow2[a][v2];
	if(res>=phi[a]) res%=phi[a],flag=1;//打标记	
	return res;
}

递归求解

inline ll dfs(int id,int dep,int limit){
	flag=0;
	if(dep==limit){
		if(a[id]>=phi[dep]){
			flag=1;//打标记
			return a[id]%phi[dep];
		} 
		return a[id];
	}
	ll now=dfs(id,dep+1,limit);//后面的幂
	if(flag) now+=phi[dep+1];//欧拉函数的性质
	return ksm(dep,now);
}

Code

#include<bits/stdc++.h>
#define ll long long
#define T (400010)
#define N (10010)
#define NN (50010)
#define M (55)
using namespace std;
struct xbk{int l,r;ll sum,tag;}t[T];
int n,m,mn;
ll P,c,a[NN],pow1[M][N],pow2[M][N],phi[M];
bool flag,f1[M][N],f2[M][N];
inline ll read(){
	ll w=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9'){
		w=(w<<3)+(w<<1)+(ch^48);
		ch=getchar();
	}
	return w;
}
inline ll Phi(ll x){
	ll res=x;
	for(ll i=2;i*i<=x;i++){
		if(x%i==0){
			res=res/i*(i-1);
			while(x%i==0) x/=i;
		}
	}
	if(x>1) res=res/x*(x-1);
	return res;		
}
inline void oula(){
	ll tmp=P;
	phi[0]=P;
	while(tmp>1) tmp=Phi(tmp),phi[++mn]=tmp;
	phi[++mn]=1;
	for(int i=0;i<=mn;i++){
		pow1[i][0]=1;
		for(int j=1;j<=10000;j++){
			pow1[i][j]=pow1[i][j-1]*c;
			if(pow1[i][j]>=phi[i]) f1[i][j]=1,pow1[i][j]%=phi[i];
			f1[i][j]|=f1[i][j-1];
		}
	}
	for(int i=0;i<=mn;i++){
		pow2[i][0]=1;
		for(int j=1;j<=10000;j++){
			pow2[i][j]=pow2[i][j-1]*pow1[i][10000];
			if(pow2[i][j]>=phi[i]) f2[i][j]=1,pow2[i][j]%=phi[i];
			f2[i][j]|=f2[i][j-1];
		}
	}
	return;
}
inline ll ksm(ll a,ll b){
	ll v1=b%10000,v2=b/10000;
	flag|=f1[a][v1]|f2[a][v2];
	ll res=pow1[a][v1]*pow2[a][v2];
	if(res>=phi[a]) res%=phi[a],flag=1;	
	return res;
}
inline ll dfs(int id,int dep,int limit){
	flag=0;
	if(dep==limit){
		if(a[id]>=phi[dep]){
			flag=1;
			return a[id]%phi[dep];
		} 
		return a[id];
	}
	ll now=dfs(id,dep+1,limit);
	if(flag) now+=phi[dep+1];
//	cout<<"now="<<now<<endl;
	return ksm(dep,now);
}
inline void update(int p){
	t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%P;
	t[p].tag=min(t[p<<1].tag,t[p<<1|1].tag);
}
inline void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(t[p].l==t[p].r){
		t[p].sum=a[l];
		t[p].tag=0;
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	update(p);
}
inline void change(int p,int l,int r){
	if(t[p].tag>=mn) return;
	if(t[p].l==t[p].r){
		t[p].tag++;
		t[p].sum=dfs(t[p].l,0,t[p].tag);
//		cout<<"p="<<p<<endl;
//		cout<<t[p].sum<<endl;
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) change(p<<1,l,r);
	if(r>mid) change(p<<1|1,l,r);
	update(p);
}
inline ll ask(int p,int l,int r){
	if(t[p].l>=l&&t[p].r<=r) return t[p].sum;
	int mid=(t[p].l+t[p].r)>>1;
	ll res=0;
	if(l<=mid) res+=ask(p<<1,l,r);
	if(r>mid) res+=ask(p<<1|1,l,r);
	return res%P;
}
int main(){
	n=read(),m=read(),P=read(),c=read();
	for(int i=1;i<=n;i++) a[i]=read();
	oula();
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int opt=read(),l=read(),r=read();
		if(!opt) change(1,l,r);
		else printf("%lld\n",ask(1,l,r));
	}
	return 0;
}

完结撒花❀

上一篇:欧拉函数


下一篇:2.26