【SHOI2017】相逢是问候【扩展欧拉定理】【复杂度分析】【线段树】

题意：给定一个长度为 $n$ 的序列 $a_i$，维护 $m$ 次操作：

区间执行 $a_i\leftarrow c^{a_i}$；

区间求和 模 $p$。

其中 $p,c$ 对所有操作相同。

$n,m\le 5\times 10^4,p\le 10^8$

不建议写，真的浪费生命

根据扩展欧拉定理，显然修改 $O(\log p)$ 次就没用了，所有数总共只会修改 $O(n\log P)$ 次。

但是暴力的话循环是占复杂度的，我们需要快速判断某个区间是否还需要修改。

似乎就只能线段树了？

暴力预处理出每个数 $\phi 60$ 次内的结果，然后线段树维护区间修改次数最小值和当前的区间和。修改的时候如果当前区间最小修改次数达到 $60$ 就退出，否则暴力递归。

复杂度 $O(n{\log }^{2}P)$ ，会被卡，根号预处理快速幂可以 $O(n\log P)$ 。

听上去还挺美好，然而这题最恶心的地方在判断扩展欧拉定理的适用条件……

方法是在快速幂（或预处理幂）的时候记录是否取过模。

Q：如何证明不会出现 $x>\phi (p),c^{x\%\phi (p)+\phi (p)}<p$ ，然后继续迭代的时候崩掉的情况？

A：实际上 $c^{\phi (p)}\ge p$ 一般都是对的。

考虑计算 $\phi (p)$ 的一个很松的下界：$\phi (p)$ 考虑了每个质因子 $x$ ，然后 $p\leftarrow p\times \frac{x-1}{x}$

根据糖水原理，这个 $x$ 越小效果会越明显。而 $x$ 小的时候能得到的质因子也会更多。

而 $10^8$ 以内的数最多只有 $8$ 个质因子，所以可以估算一个下界 $\frac{\phi (p)}{p}\ge \frac{1}{2}\times \frac{2}{3}\times \frac{4}{5}\times \cdots \times \frac{18}{19}\approx 0.17$

相当于要证明： $2^{p/7}\ge p$ ，前者增长远快于后者，$p$ 足够大（也就几十）的时候该式成立。

小数据暴力打表知只有个 $p=6$ ，但 $6$ 只能取 $2$ 次 $\phi$ ，所以也崩不了

证毕

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <vector> #include <bitset> #include <utility> #define MAXN 50005 #define re register using namespace std; typedef long long ll; int n,q,c,flag; inline int mul(const int& a,const int& b,const int& MOD) {ll c=(ll)a*b;if (c>=MOD) flag=1;return c%MOD; } int m[60],len; typedef pair<int,int> pi; const int N=2e4; pi p1[60][N+5],p2[60][N+5];//i,i*10000 inline void init() {for (int T=0;T<=len;T++){p1[T][0]=p2[T][0]=make_pair(1,0);flag=0;for (int i=1;i<N;i++) p1[T][i].first=mul(p1[T][i-1].first,c,m[T]),p1[T][i].second=flag;p2[T][1].first=mul(p1[T][N-1].first,c,m[T]),p2[T][1].second=flag;for (int i=2;i<=N;i++) p2[T][i].first=mul(p2[T][i-1].first,p2[T][1].first,m[T]),p2[T][i].second=flag;} } inline int qpow(int p,int i) {pi x=p1[i][p%N],y=p2[i][p/N];flag|=(x.second|y.second);return mul(x.first,y.first,m[i]); } inline int calcphi(int x) {int ans=1;for (int i=2;i*i<=x;i++)if (x%i==0){ans*=i-1,x/=i;while (x%i==0) ans*=i,x/=i;}if (x>1) ans*=x-1;return ans; } int a[MAXN][60]; #define lc p<<1 #define rc p<<1|1 int sum[MAXN<<2],mcnt[MAXN<<2]; inline void update(int p){mcnt[p]=min(mcnt[lc],mcnt[rc]),sum[p]=(sum[lc]+sum[rc])%m[0];} void build(int p,int l,int r) {if (l==r){scanf("%d",&a[l][0]);for (int i=1;i<=len;i++){flag=0;int x=a[l][0];for (int j=i;j>=1;j--) x=qpow(x+m[j]*flag,j-1);a[l][i]=x;}sum[p]=a[l][0];return;}int mid=(l+r)>>1;build(lc,l,mid);build(rc,mid+1,r);update(p); } void modify(int p,int l,int r,int ql,int qr) {if (qr<l||r<ql) return;if (mcnt[p]>=len) return;if (l==r) return (void)(sum[p]=a[l][++mcnt[p]]);int mid=(l+r)>>1;modify(lc,l,mid,ql,qr),modify(rc,mid+1,r,ql,qr);update(p); } int query(int p,int l,int r,int ql,int qr) {if (qr<l||r<ql) return 0;if (ql<=l&&r<=qr) return sum[p];int mid=(l+r)>>1;return (query(lc,l,mid,ql,qr)+query(rc,mid+1,r,ql,qr))%m[0]; } int main() {scanf("%d%d%d%d",&n,&q,&m[0],&c);for (len=1;(m[len]=calcphi(m[len-1]))>1;++len);m[++len]=1;init();build(1,1,n);while (q--){int t,l,r;scanf("%d%d%d",&t,&l,&r);if (t==0) modify(1,1,n,l,r);else printf("%d\n",query(1,1,n,l,r));}return 0; }

总结

以上是生活随笔为你收集整理的【SHOI2017】相逢是问候【扩展欧拉定理】【复杂度分析】【线段树】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。