题意
给定序列\(w_1,w_2,...,w_n\)和\(q\)组询问,对于每组询问,求
当然,需要对这个值膜\(m\)
(hexo渲染多重幂有问题,只好放原题图片了)
\(1 \leq n \leq 1e5\), \(1 \leq m \leq 1e9\), \(1 \leq q \leq 1e5\)
思路
考虑扩展欧拉定理:
\[
a^b = \left\{
\begin{array}{lcl}
a^b && {b < φ(p)} \\
a^{b \bmod φ(p) + φ(p) } && {b \geq φ(p)}\\
\end{array}
\right.
\]
由于\(p \geq 2\)时\(φ(p)\)为偶数,故\(p = φ(p)\)的下降速度是log级别的,换句话说经过最多\(log(p)\)次迭代之后\(p\)便会变为1.由于\(x \bmod 1 == 0\),我们在\(l == r\)或者\(p == 1\)时便可跳出递归,单组询问的复杂度为\(O(logp)\),可以接受
在具体实现时,应预处理出\(p,φ(p),φ(φ(p)),...,1\)来减少时间开销,同时修改快速幂来适应扩欧定理(upd函数),细节见代码
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
ll raw[maxn],n,mod;
map<ll,ll>vis;
ll phi(ll x){
int m = (ll)sqrt(x+0.5);
ll tans = x;
for(int i = 2;i <= m;i++)if(!(x%i)){
tans = tans/i*(i-1);
while(!(x%i))x /= i;
}
if(x > 1)tans = tans / x * (x-1);
return tans;
}
inline ll upd(ll x,ll p){
return x<p?x:x%p+p;
}
ll Pow(ll x,ll d,ll p){
ll tans = 1;
if(d == 0)return 1;
ll a = Pow(x,d/2,p);
tans = upd(a*a,p);
if(d%2)tans = upd(tans*x,p);
return upd(tans,p);
}
ll cal(ll l,ll r,ll p){
if(l == r or p == 1)return upd(raw[l],p);
else return Pow(raw[l],cal(l+1,r,vis[p]),p);
}
int main(){
cin >> n >> mod;
ll qwq = mod;
while(qwq != 1){
vis[qwq] = phi(qwq);
qwq = vis[qwq];
}
vis[1] = 1;
for(int i = 1;i <= n;i++)cin >> raw[i];
int q;
cin >> q;
while(q--){
int l,r;
cin >> l >> r;
cout << cal(l,r,mod)%mod << endl;
}
return 0;
}
|
\[
f(n) = O(g(n))
\\ \Rightarrow f(n) \leq c_f \cdot g(n) \\
\Rightarrow \frac{1}{f(n)} \geq \frac{1}{c_f\cdot g(n)}\\
\Rightarrow \frac{1}{g(n)} \leq c_f\cdot \frac{1}{f(n)} 对于n >= n_f\\
故有 \frac{1}{g(n)} = O(\frac{1}{f(n)})
\]