题解 P3747 【[六省联考2017]相逢是问候】
诗乃
2019-10-10 16:23:12
前置芝士扩展欧拉定理：
引理：一个数至多取$O(log)$次欧拉函数会变为1.
口胡证明：对于偶数，所有小于它的偶数都与它不互质，其欧拉函数至少为其$\frac{1}{2}$。对于奇数，其欧拉函数必是偶数。证毕。
由此可得某数在修改$O(log)$次之后将不再改变。
考虑暴力分块。
将序列分为$\frac{n}{B}$个大小为$B$的块。修改时暴力修改整块与散块，若某一次修改后发现当前块没有数字被改变，说明继续修改这个块也不再生效，打上标记不再修改。
考虑如何修改单点。
记录每个位置的修改次数，用扩展欧拉定理直接嵌套求解，容易写出像这样的代码：
```cpp
void getans(int x, int t, int p) {
//x为当前位置初始值，t为修改次数，p为当前模数。
if(!t) return x%p;
if(p==1) return 0;
int b = getans(x, t-1, phi[p])+phi[p];
return pwc(b, p);
//其中pwc(b, p)表示求c^b mod p的值。
}
```
这样写显然是有一点点小问题的，代码中并没有判断$b$与$\varphi(p)$的大小，引入一个结构体来存储数据是否已经超过$p$即可解决此问题。
```cpp
struct Node {int x, flag;};
Node getans(int x, int t, int P) {
if(!t) return (Node) {x%P, x>=P};
if(P == 1) return (Node) {0, 1};
Node tmp = getans(x, t-1, phi[P]);
int b = tmp.x + phi[P] * tmp.flag;
return pwc(b, P); //在pwc()中也需要判断，详见代码。
}
```
这样看起来单点修改的时间是$O(log^2n)$的，难以接受。考虑优化快速幂。
考虑暴力分块。设最大指数为$V$，则可以对于每一个模数预处理出以下两个信息：
1、$c^1,c^2,c^3,c^4,c^5....,c^{\sqrt{V}}$。
2、$c^{\sqrt{V}},c^{2\sqrt{V}},c^{3\sqrt{V}},c^{4\sqrt{V}},....c^{V}$。
对于每一个指数$b<V$，有：
$$b=k\sqrt{V}+t(k \in N,t≤\sqrt{V})$$
由于模数最多只有$O(logn\sqrt{V})$预处理$O(1)$求解$c$的幂次方。
由此达成了$O(logn)$单点修改。
随便假设一下$log(n),log(p)$同阶来分析复杂度。(懒）
由于每个块最多被整块修改$O(logn)$次，每次修改复杂度为$O(Blogn)$，共有$O(\frac{n}{B})$个块，因此整块修改的复杂度为均摊$O(nlog^2n)$，散块修改复杂度$O(nBlogn)$。
对于询问操作，复杂度为$O(nB+\frac{n^2}{B})$
当$B=\sqrt{\frac{n}{log_2n}}$的时候复杂度最优，为$O(nlog^2n+(nlogn)^{\frac{3}{2}})$
可以草过本题。上代码：
```cpp
#include <bits/stdc++.h>
#define bl(x) ((x-1)/siz+1)
#define L(x) (x-1)*siz+1
#define R(x) std::min(x*siz, n)
using namespace std;
const int MAXN = 50050, MAXB = 250, GSM = 12000, MAXV = 1e8;
int s[MAXB], a[MAXN], tag[MAXN], n, m, p, c, siz, tms[MAXN], ori[MAXN], notp[MAXV+5], phi[MAXV+5], prime[MAXV+5];
int id[MAXV+5], _c[150][GSM+5], __c[150][GSM+5], ccc, cntp, _b[150][GSM+5], __b[150][GSM+5];
struct Node {int x, flag;};
void read(int &x) {
char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
void write(int x) {if(x > 9) write(x / 10); putchar(x % 10 + 48);}
int Getphi(int x) {
int ans = x;
for(int i = 2; i * i <= x; ++i)
if(x % i == 0) {
ans = ans / i * (i-1);
while(x % i == 0) x /= i;
}
if(x > 1) ans = ans / x * (x-1);
return ans;
}
void init(int P) {
id[P] = ++ccc; _c[id[P]][0] = __c[id[P]][0] = 1;
for(int i = 1; i <= GSM; ++i) {
_c[id[P]][i] = 1ll*_c[id[P]][i-1]*c%P;
_b[id[P]][i] = (_b[id[P]][i-1] || _c[id[P]][i-1]*c >= P);
}
__c[id[P]][1] = _c[id[P]][GSM]; __b[id[P]][1] = _b[id[P]][GSM];
for(int i = 2; i <= GSM; ++i) {
__c[id[P]][i] = 1ll*__c[id[P]][i-1]*__c[id[P]][1]%P;
__b[id[P]][i] = (__b[id[P]][i-1] || __c[id[P]][i-1]*_c[id[P]][1] >= P);
}
}
Node pwc(int b, int P) {
return (Node) {1ll*__c[id[P]][b/GSM]*_c[id[P]][b%GSM]%P, __b[id[P]][b/GSM]||_b[id[P]][b%GSM]||__c[id[P]][b/GSM]*_c[id[P]][b%GSM]>=P};
}
Node getans(int x, int t, int P) {
if(!t) return (Node) {x%P, x>=P};
if(P == 1) return (Node) {0, 1};
Node tmp = getans(x, t-1, phi[P]);
int b = tmp.x + phi[P] * tmp.flag;
return pwc(b, P);
}
void update(int b) {for(int i = L(b); i <= R(b); ++i) s[b] = (s[b] + a[i]) % p;}
void modify(int i) {
s[bl(i)] -= a[i]; ++tms[i];
a[i] = getans(ori[i], tms[i], p).x;
s[bl(i)] += a[i]; s[bl(i)] = (s[bl(i)] + p) % p;
}
void work(int b) {
if(tag[b]) return; tag[b] = 1;
for(int i = L(b); i <= R(b); ++i) {
int t = a[i]; modify(i);
if(t != a[i]) tag[b] = 0;
}
}
int main() {
read(n); read(m); read(p); read(c); siz = max(1.0, sqrt(n/log2(n)));
int tmp = p;
for(; tmp > 1; tmp = phi[tmp]) phi[tmp] = Getphi(tmp), init(tmp); init(1);
for(int i = 1; i <= n; ++i) read(a[i]), ori[i] = a[i];
for(int i = 1; i <= bl(n); ++i) update(i);
for(int opt, l, r; m--; ) {
read(opt); read(l); read(r);
if(!opt) {
if(bl(l) == bl(r))
for(int i = l; i <= r; ++i) modify(i);
else {
for(int i = l; i <= R(bl(l)); ++i) modify(i);
for(int i = bl(l)+1; i <= bl(r)-1; ++i) work(i);
for(int i = L(bl(r)); i <= r; ++i) modify(i);
}
} else {
if(bl(l) == bl(r)) {
int res = 0;
for(int i = l; i <= r; ++i) res = (res + a[i]) % p;
write(res); putchar('\n');
} else {
int res = 0;
for(int i = l; i <= R(bl(l)); ++i) res = (res + a[i]) % p;
for(int i = bl(l)+1; i <= bl(r)-1; ++i) res = (res + s[i]) % p;
for(int i = L(bl(r)); i <= r; ++i) res = (res + a[i]) % p;
write(res); putchar('\n');
}
}
}
}
```