洛谷3747 [六省联考2017]相逢是问候

欧拉定理的扩展

Posted by yjjr's blog on March 19, 2018

标签:线段树,欧拉定理

题目

题目传送门

题目描述

Informatik verbindet dich und mich.

信息将你我连结。

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

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

  • 表示将第 l 个到第 r 个数中的每一个数 替换为 ,即 c 的 次方,其中 c 是输入的一个常数,也就是执行赋值

  • 1 l r 求第 l 个到第 r 个数的和,也就是输出:

因为这个结果可能会很大,所以你只需要输出结果 mod p 的值即可。

输入输出格式

输入格式

第一行有三个整数 n; m; p; c,所有整数含义见问题描述。

接下来一行 n 个整数,表示 a 数组的初始值。

接下来 m 行,每行三个整数,其中第一个整数表示了操作的类型。

如果是 0 的话,表示这是一个修改操作,操作的参数为 l; r。

如果是 1 的话,表示这是一个询问操作,操作的参数为 l; r。

输出格式

对于每个询问操作,输出一行,包括一个整数表示答案 mod p 的值。

输入输出样例

输入样例#1

4 4 7 2
1 2 3 4
0 1 4
1 2 4
0 1 4
1 1 3

输出样例#1

0
3

说明

• 对于 0% 的测试点,和样例一模一样;

• 对于另外 10% 的测试点,没有修改;

• 对于另外 20% 的测试点,每次修改操作只会修改一个位置(也就是 l = r),并且每个位置至多被修改一次;

• 对于另外 10% 的测试点, p = 2;

• 对于另外 10% 的测试点, p = 3;

• 对于另外 10% 的测试点, p = 4;

• 对于另外 20% 的测试点, n ≤ 100; m ≤ 100;

• 对于 100% 的测试点, 1 ≤ n ≤ 50000; 1 ≤ m ≤ 50000; 1 ≤ p ≤ 100000000; 0 < c <p; 0 ≤ ai < p。

分析

前置技能:欧拉定理的扩展

定理中的p可以不为质数

附上证明

然后发现一个结论

这个操作在进行log p次之后一定是个定值,之后便没有意义了

用线段树维护这个过程,如果当前区间所有节点都已经不再变化那么就不修改了

所以最坏情况下每个数会修改次,每次会修改个节点

对于一个数的快速幂需要计算次,时间复杂度就过大

所以我们需要考虑优化掉计算快速幂的那个

因为底数为确定的C,我们可以预处理,t为,然后可以快速从两个表中进行查找

code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
//**********head by yjjr**********
#define lson (x<<1)
#define rson (x<<1|1)
#define mid ((l+r)>>1)
const int maxn=5e4+6,splitnum=1e4;
int n,m,p,c,k,t;
int sum[maxn<<2],num[maxn<<2],tag[maxn<<2],a[maxn],f[maxn][100],cc[maxn][100],ex_c[maxn][100],pp[100];
inline ll qpow(int x,int y,int mod){
	ll re=1;
	while(y){
		if(y&1)re=(re*x)%mod;
		y>>=1,x=(1ll*x*x)%mod;
	}
	return re;
}
void pushup(int x){sum[x]=(sum[lson]+sum[rson])%p;tag[x]=tag[lson]+tag[rson];}
void build(int x,int l,int r){
	if(l==r){sum[x]=a[l];num[x]=0;tag[x]=r-l+1;return;}
	build(lson,l,mid);build(rson,mid+1,r);
	pushup(x);
}
void modify(int x,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr&&!tag[x])return;
	if(l==r){
		num[x]++;sum[x]=f[l][num[x]];
		if(num[x]==k)tag[x]--;
		return;
	}
	if(ql<=mid)modify(lson,l,mid,ql,qr);
	if(qr>mid)modify(rson,mid+1,r,ql,qr);
	pushup(x);
}
inline int query(int x,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr)return sum[x];
	ll re=0;
	if(ql<=mid)re+=query(lson,l,mid,ql,qr);
	if(qr>mid)re+=query(rson,mid+1,r,ql,qr);
	return re%p;
}
inline int phi(int x){
	int re=x,y=sqrt(x);
	rep(i,2,y)
		if(!(x%i)){while(!(x%i))x/=i;re=re/i*(i-1);}
	if(x-1)re=re/x*(x-1);
	return re;
}
inline int q_p(int x,int a,int num){
	if(a<=splitnum)return cc[a][num];
	return (1ll*ex_c[a/splitnum][num]*cc[a%splitnum][num])%pp[num];
}
inline int get_(int x,int num,int d){
	if(!num)if(x>pp[d])return x%pp[d];else return x;
	t=get_(x,num-1,d+1);
	double q=log(1.0/x*pp[d+1])/log(1.0*c)-num+1;
	if(q<=0)t+=pp[d+1];
	return q_p(c,t,d);
}
void Pre(){
	rep(i,0,splitnum)
		rep(j,0,k){
			cc[i][j]=qpow(c,i,pp[j]);
			int g=qpow(c,splitnum,pp[j]);
			ex_c[i][j]=qpow(g,i,pp[j]);
		}
	rep(i,1,n)
		if(a[i]==0){
			f[i][1]=1;
			rep(j,2,k)f[i][j]=get_(1,j-1,0);
		}else rep(j,1,k)f[i][j]=get_(a[i],j,0);
}		
int main()
{
	n=read(),m=read(),p=read(),c=read();
	k=0;pp[0]=p;
	while(pp[k]-1){k++;pp[k]=phi(pp[k-1]);}
	k++;pp[k]=1;
	rep(i,1,n)a[i]=read();
	Pre();
	build(1,1,n);
	while(m--){
		int opt=read(),l=read(),r=read();
		if(opt==0)modify(1,1,n,l,r);
		if(opt==1)printf("%d\n",query(1,1,n,l,r));
	}
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr