題意：給定一個長度為 $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 \text{?}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 ?\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】相逢是问候【扩展欧拉定理】【复杂度分析】【线段树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。