- 传送门 -
http://www.lydsy.com/JudgeOnline/problem.php?id=4869
Time Limit: 40 Sec Memory Limit: 512 MB
Submit: 823 Solved: 250
[Submit][Status][Discuss]
Description
Informatikverbindetdichundmich.
信息将你我连结。B君希望以维护一个长度为n的数组，这个数组的下标为从1到n的正整数。一共有m个操作，可以
分为两种：0 l r表示将第l个到第r个数（al,al+1,...,ar）中的每一个数ai替换为c^ai，即c的ai次方，其中c是
输入的一个常数，也就是执行赋值ai=c^ai1 l r求第l个到第r个数的和，也就是输出：sigma(ai),l<=i<=rai因为
这个结果可能会很大，所以你只需要输出结果mod p的值即可。
Input
第一行有三个整数n,m,p,c，所有整数含义见问题描述。
接下来一行n个整数，表示a数组的初始值。
接下来m行，每行三个整数，其中第一个整数表示了操作的类型。
如果是0的话，表示这是一个修改操作，操作的参数为l,r。
如果是1的话，表示这是一个询问操作，操作的参数为l,r。
1 ≤ n ≤ 50000, 1 ≤ m ≤ 50000, 1 ≤ p ≤ 100000000, 0 < c <p, 0 ≤ ai < p
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
- 题意 -
给定区间, 两种操作:
0 l r : 将区间[l, r]内的元素 (a_i) 改为 (c^{a_i}) .
1 l r : 求区间[l, r]内元素的总和.
- 思路 -
首先，有欧几里得定理的扩展(欧几里得定理EXT):
(a^bequiv a^{b \%varphi(p)+varphi(p)}) (mod p) , gcd(a, p) (
eq) 1 且 b > (varphi(p))
证明如下:
证明一 证明二
(不过反正我是一个都没看懂...逃...)
假设当前a[i]为x
我们对其进行一次操作有:
(c^xequiv c^{x \%varphi(p)+varphi(p)}) , x > $ varphi(p)$ (mod p) (就和上面一样)
对其进行两次操作的话则变成了求模p意义下的 (c^{c^x}) ：
此时 c 的上标变成了(c^x) , 我们设 (d = c^x), 即((c^{c^x}) = (c^d)), 则有
(c^dequiv c^{d \%varphi(p)+varphi(p)}) (mod p)
即(c^{c^x}equiv c^{{c^x} \%varphi(p)+varphi(p)}) (mod p)
这时我们发现右式的上标中出现了一个熟悉的东西
({c^x} \%varphi(p))
把(varphi(p))视为标准式中的p, 我们又可以对其进行转化了
先设 d = (varphi(p))
({c^x}equiv c^{x \%varphi(d)+varphi(d)}) (mod d)
即({c^x}equiv c^{x \%varphi(varphi(p))+varphi(varphi(p))}) (mod (varphi (p)))
综上:
(c^{c^x}equiv {c^{{c^x} \%varphi(p)+varphi(p)} equiv c^{c^{x \%varphi(varphi(p))+varphi(varphi(p))} +varphi(p)}}) (mod p)
那么当我们操作多次时, $x %varphi(...(varphi(p))) $ 中多次对p取欧拉函数会变成1, 于是顶层的c的上标就会变成
x%1 + 1 = 1
式子大概长这样:(c^{...^{c^{x\%varphi(...(varphi(p)))+varphi(...(varphi(p)))}}})
(uparrow) (uparrow)
这是0 这是1
化简后: (c^{...^c})
也就是说, 原式的顶层的上标一定是会先 %1 再 +1 然后变成1.
我们将此时(化简后)c的个数称为有效层数.
再进行一次操作的话, 相当于再增加一层c.
此时第二层的情况就相当与之前的顶层的情况(因为自底层向上数,每一层的处理是一样的,与层数,上标无关), 于是顶层就没有用了, 因为它会被次层整个先 %1 再 +1.
这样顶层就没了, 有效层数不变.
似乎只要处理到(varphi(p) = 1) 就可以了, 那是不是只要展开到(varphi(2) = 1)呢?
我们看初始值x=0的情况:
展开到(varphi(2) = 1)时:
(c^{...^{c^{0\%varphi(...(varphi(p)))+varphi(...(varphi(p)))}}}equiv c^{...^{(c^{0\%varphi (2)+varphi(2)})\%2}}equiv c^{...^{c\%2}})
展开到(varphi(1) = 1)时:
(c^{...^{c^{c^{0\%varphi(...(varphi(p)))+varphi(...(varphi(p)))}}}}equiv c^{...{c^{(c^{0\%varphi (1)+varphi(1)})\%1}}}equiv c^{...{c^{0\%varphi(2)}\%2}}equiv c^{...1\%2})
(uparrow)
省略的c是一样多的
我们发现 c%2 不一定等于 1 , 所以此时需要再展开一层.
细节见代码.
PS :
噫!
加上写题解这题大概花了两天!
(事实上是一直在看题解然而看不懂最后还是问了小伙伴)
所以说有小伙伴的最好去问小伙伴!!!
(神犇请自动忽略上一句话)
可是还是没有看懂怎么搞掉快速幂的那个log, 也没有搞懂定理的证明...
我还是太水...
- 代码 -
#include<cstdio>
#define ls rt << 1
#define rs rt << 1 | 1
using namespace std;
typedef long long ll;
const int M = 5e4 + 5;
const int N = 1e4 + 5;
struct segtree {
int tag, s;
}tr[M<<2];
int a[M];
int pi[30]; //phi
int pri[N + 5]; //素数
int isp[N + 5];
int n, m, p, c, t, k;
template <typename T> T Min (T a, T b) { return a < b ? a : b; }
int Phi(int x) {
int ans = x;
for (int i = 1; i <= k && pri[i] * pri[i] <= x; ++i) {
if (x % pri[i] == 0)
ans = ans / pri[i] * (pri[i] - 1);
while (x % pri[i] == 0)
x /= pri[i];
}
if (x > 1) ans = ans / x * (x-1);
return ans;
}//朴素的欧拉函数求法
void Init() {
for (int i = 2; i <= N; ++i) {
if (!isp[i]) pri[++k] = i;
for (int j = 1; j <= k; ++j) {
if (i * pri[j] > N) break;
isp[pri[j]*i] = 1;
if (i % pri[j] == 0) break;
}
}//预处理出素数用来算欧拉
pi[t] = p;
while (pi[t] != 1) pi[++t] = Phi(pi[t-1]);
pi[++t] = 1;//求我们要用到的欧拉函数
}
void Pushup(int rt) {
tr[rt].s = (tr[ls].s + tr[rs].s) % p;
tr[rt].tag = Min(tr[ls].tag, tr[rs].tag);
}
void Build(int rt, int l, int r) {
if (l == r) {
scanf("%d", &a[l]);
a[l] %= p;
tr[rt].s = a[l];
return;
}
int mid = l + r >> 1;
Build(ls, l, mid);
Build(rs, mid + 1, r);
Pushup(rt);
}
int QP(int a, int b, int mod, int &f) {
int ans = 1;
while (b) {
if (b & 1) {
if (1ll * ans * a >= mod) f = 1;
ans = 1ll * ans * a % mod;
}
if (1ll * a * a >= mod) f = 1;
a = 1ll * a * a % mod;
b >>= 1;
} //快速幂, 同时判断f, f含义见下
return ans;
}
int C(int a, int x) {
int tmp = a;
if (tmp > pi[x]) tmp = tmp%pi[x] + pi[x];
for (int i = x, f; i > 0; --i) {
f = 0; tmp = QP(c, tmp, pi[i-1], f);
if (f) tmp += pi[i-1]; //f用来判断某情况下是否要加pi[i-1](c^tmp是否不小于pi[i-1])
}
return tmp;
}
void Modify(int x, int y, int rt, int l, int r) {
if (tr[rt].tag >= t) return; //该区间每个数都被操作了t次, 不再改变
if (l == r) {
tr[rt].s = C(a[l], ++tr[rt].tag) % p;
return;
}
int mid = l + r >> 1;
if (x <= mid) Modify(x, y, ls, l, mid);
if (mid < y) Modify(x, y, rs, mid+1, r);
Pushup(rt);
}
int Getsum(int x, int y, int rt, int l, int r) {
if (x <= l && r <= y) return tr[rt].s % p;
int mid = l + r >> 1;
int ans = 0;
if (x <= mid) ans = (ans + Getsum(x, y, ls, l, mid)) % p;
if (mid < y) ans = (ans + Getsum(x, y, rs, mid+1, r)) % p;
return ans;
}
int main() {
scanf("%d%d%d%d", &n, &m, &p, &c);
Init();
Build(1, 1, n);
int f, l, r;
while (m --) {
scanf("%d%d%d", &f, &l, &r);
if (f == 0) Modify(l, r, 1, 1, n);
else printf("%d
", Getsum(l, r, 1, 1, n));
}
}