BZOJ4869【SHOI2017】相逢是问候 <扩展欧拉定理+线段树>

Problem

【SHOI2017】相逢是问候

$\mathrm{Time\;Limit:\;40\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$

Description

$\mathrm{B君}$希望以维护一个长度为$n$的数组，这个数组的下标为从$1$到$n$的正整数。
一共有$m$个操作，可以分为两种：

1. $0\;l\;r$：表示将第$l$个到第$r$个数($a_l,a_{l+1},\cdots,a_r$)中的每一个数$a_i$替换为$c^{a_i}$，其中$c$是一个常数
2. $1\;l\;r$：求第$l$个到第$r$个数的和，即$\sum_{i=l}^{r}a_i$

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

Input

第一行有三个整数$n,m,p,c$。
接下来一行$n$个整数，表示a数组的初始值。
接下来$m$行，每行三个整数，其中第一个整数表示了操作的类型。
如果是$0$，表示这是一个修改操作，操作的参数为$l,r$。
如果是$1$，表示这是一个询问操作，操作的参数为$l,r$。

Output

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

Sample Input

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

Sample Output

0
3

HINT

$1\le n\le5\times10^4$, $1\le m\le5\times10^4$, $1\le p\le10^7$, $0<c<p$, $0\le a_i<p$

Source

黑吉辽沪冀晋六省联考
鸣谢xlk授权本OJ使用权
鸣谢多名网友提供正确数据，已重测！

标签：扩展欧拉定理 线段树

Solution

数论和数据结构结合。

扩展欧拉定理：$x^k\equiv x^{\phi(p)+k\%\phi(p)}\mod{p}\;(k\ge\phi(p))$。
由于$p$最多$\log p$次取$\phi$后变为定值$1$，所以可以暴力修改，类似区间取模的线段树，需要注意每层指数模的是$p$取多少次$\phi$的值。
因为修改时需要计算$\phi$和快速幂，总复杂度为$O(n\log^3n)$。预处理$\phi$可将复杂度缩小为$O(n\log^2n)$。

Code

#include <bits/stdc++.h>
#define MAX_N 50000
#define mid ((s+t)>>1)
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, p, c, k;
int a[MAX_N+5]; lnt phi[MAX_N+5];
lnt tr[MAX_N<<2]; int num[MAX_N<<2];
int getphi(int n) {
    int ret = n;
    for (int i = 2; i*i <= n; i++)
        if (n%i == 0) {
            ret = ret/i*(i-1);
            while (n%i == 0) n /= i;
        }
    if (n^1) ret = ret/n*(n-1);
    return ret;
}
lnt pow(lnt x, lnt k, lnt MOD) {
    lnt ret = 1;
    for (; k; k >>= 1, x = 1LL*x*x%MOD)
        if (k&1) ret = 1LL*x*ret%MOD;
    return ret;
}
lnt calc(lnt x, int k) {
    for (int i = k; i; i--) {
        if (x >= phi[i]) x = x%phi[i]+phi[i];
        x = pow(c, x, phi[i-1]), x = x ? x : phi[i-1];
    }
    return x;
}
void build(int v, int s, int t) {
    if (s == t) {tr[v] = a[s]%p; return;}
    build(v<<1, s, mid), build(v<<1|1, mid+1, t);
    tr[v] = (tr[v<<1]+tr[v<<1|1])%p;
}
void modify(int v, int s, int t, int l, int r) {
    if (num[v] >= k) return;
    if (s == t) {tr[v] = calc(a[s], ++num[v]); return;}
    if (l <= mid) modify(v<<1, s, mid, l, r);
    if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r);
    tr[v] = (tr[v<<1]+tr[v<<1|1])%p;
    num[v] = min(num[v<<1], num[v<<1|1]);
}
lnt query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return tr[v]; lnt ret = 0;
    if (l <= mid) (ret += query(v<<1, s, mid, l, r)) %= p;
    if (r >= mid+1) (ret += query(v<<1|1, mid+1, t, l, r)) %= p;
    return ret;
}
void init() {
    phi[0] = p;
    for (int i = p; i^1; )
        phi[++k] = i = getphi(i);
    phi[++k] = 1;
}
int main() {
    read(n), read(m), read(p), read(c);
    for (int i = 1; i <= n; i++) read(a[i]);
    init(), build(1, 1, n);
    while (m--) {
        int opt, l, r; read(opt), read(l), read(r);
        if (opt == 0) modify(1, 1, n, l, r);
        if (opt == 1) printf("%lld\n", query(1, 1, n, l, r));
    }
    return 0;
}