题解：CF1109E Sasha and a Very Easy Test
chlchl
·
·
题解
upd 2024.9.11 修正一处笔误。
也是好起来了，晚自习跑机房集训了。
因为变量重名调了半个晚上，太菜了 qwq。
Solution
但不是质数，单点除法就不能用逆元，我们是没有办法处理带模除法的。
质数要求太过苛刻，我们可以用欧拉定理：
$$x^{\varphi(x)}\equiv 1\pmod p,\quad
\gcd(x,p)=1$$
此时 $x$ 的逆元即为 $x^{\varphi(x)-1}$。
但是我们仍然需要除数和 $mod$ 互质，所以考虑如何把它变得互质。显然地，把不互质的部分去掉不就互质了吗？
这启发我们分开维护。先将 $mod$ 进行唯一分解，可以发现不同的质因子不会超过 $9$ 个。那么对于除法给出的每一个 $x$，我们可以单独处理 $x$ 中含有的 $mod$ 的因子并且把它们干掉，剩下的直接求逆元就好了。
具体地，用线段树维护区间和与区间乘标记。由于除法是单点除法，所以在线段树中每次都会下到最底层。
因此，如果我们维护一个数组 $cnt$ 表示当前节点的乘法标记含有 $mod$ 的因子的个数，那么单点除法的时候只需要在叶结点暴力下放所有懒标记之后对 $cnt$ 进行修改就行了。
而区间乘法的时候就把 $x$ 拆成上述两部分，分别加到普通乘法标记和 $cnt$ 数组中即可。
其实你可以直接将 $cnt$ 数组理解为一个数（反正将它们快速幂后乘起来本来就是 $x$ 的一个因数），只是我们单独将它的分解形式拎出来储存了而已，这样在写代码的时候就方便你思考该对它干什么了。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n, q, len;
int p, phi, ys[12];
int exp(int a, int b){
int cnt = 1;
while(b){
if(b & 1)
(cnt *= a) %= p;
(a *= a) %= p, b >>= 1;
}
return cnt;
}
struct NUM{
int x, cnt[12];
NUM(){}
NUM(int n){
memset(cnt, 0, sizeof(cnt));
x = 0;
if(n == 1){
x = 1;
return ;
}
for(int i=1;i<=len;i++){
while(n % ys[i] == 0)
n /= ys[i], cnt[i]++;
}//将 n 拆成两部分
x = n;
}
int calc(){
int res = x;
for(int i=1;i<=len;i++)
(res *= exp(ys[i], cnt[i])) %= p;
return res;
}//算一算这个懒标记的总和到底是多少
} a[N], tagnum[N << 2];
int val[N << 2], tag[N << 2];
#define ls(o) (o << 1)
#define rs(o) (o << 1 | 1)
void build(int o, int l, int r){
tag[o] = 1;
tagnum[o] = NUM(1);
if(l == r){
val[o] = a[l].calc();
return ;
}
int mid = (l + r) >> 1;
build(ls(o), l, mid);
build(rs(o), mid + 1, r);
val[o] = (val[ls(o)] + val[rs(o)]) % p;
}
void pushdown(int o){
(tag[ls(o)] *= tag[o]) %= p, (tag[rs(o)] *= tag[o]) %= p;
(val[ls(o)] *= tag[o]) %= p, (val[rs(o)] *= tag[o]) %= p;
(tagnum[ls(o)].x *= tagnum[o].x) %= p, (tagnum[rs(o)].x *= tagnum[o].x) %= p;
for(int i=1;i<=len;i++){
tagnum[ls(o)].cnt[i] += tagnum[o].cnt[i];
tagnum[rs(o)].cnt[i] += tagnum[o].cnt[i];
tagnum[o].cnt[i] = 0;
}//pushdown 的时候也要下传，cnt的本质和tag是一样的
tag[o] = tagnum[o].x = 1ll;
}
void update(int o, int l, int r, int s, int t, int v){
if(l >= s && r <= t){
NUM x = NUM(v);
(tagnum[o].x *= x.x) %= p;
(val[o] *= v) %= p;
(tag[o] *= v) %= p;
for(int i=1;i<=len;i++)
tagnum[o].cnt[i] += x.cnt[i];//区间乘法更新
return ;
}
int mid = (l + r) >> 1;
pushdown(o);
if(s <= mid)
update(ls(o), l, mid, s, t, v);
if(t > mid)
update(rs(o), mid + 1, r, s, t, v);
val[o] = (val[ls(o)] + val[rs(o)]) % p;
}
void update(int o, int l, int r, int pos, int v){
if(l == r){
(a[l].x *= tagnum[o].x) %= p;//p和pos搞混了是谁我不说
tagnum[o].x = 1;
for(int i=1;i<=len;i++){
a[l].cnt[i] += tagnum[o].cnt[i];
while(v % ys[i] == 0)
a[l].cnt[i]--, v /= ys[i];//一个个把v的因子除掉
tagnum[o].cnt[i] = 0;
}
(a[l].x *= exp(v, phi - 1)) %= p;//剩下部分可以直接求逆元
val[o] = a[l].calc();//注意更新此时的单点和
return ;
}
int mid = (l + r) >> 1;
pushdown(o);
if(pos <= mid)
update(ls(o), l, mid, pos, v);
else
update(rs(o), mid + 1, r, pos, v);
val[o] = (val[ls(o)] + val[rs(o)]) % p;
}
int query(int o, int l, int r, int s, int t){
if(l >= s && r <= t)
return val[o];
int mid = (l + r) >> 1; int res = 0;
pushdown(o);
if(s <= mid)
(res += query(ls(o), l, mid, s, t)) %= p;
if(t > mid)
(res += query(rs(o), mid + 1, r, s, t)) %= p;
return res;
}
main(){
scanf("%lld%lld", &n, &p);
int m = p; phi = p;
for(int i=2;i*i<=m;i++){
if(m % i == 0){
ys[++len] = i;
phi = phi * (i - 1ll) / i;//顺便求一下 phi(mod)
while(m % i == 0)
m /= i;
}
}
if(m > 1)
ys[++len] = m, phi = phi * (m - 1ll) / m;
for(int i=1,x;i<=n;i++){
scanf("%lld", &x);
a[i] = NUM(x);
}
build(1, 1, n);
scanf("%lld", &q);
while(q--){
int op, l, r; int x;
scanf("%lld", &op);
if(op == 1){
scanf("%lld%lld%lld", &l, &r, &x);
update(1, 1, n, l, r, x);
}
if(op == 2){
scanf("%lld%lld", &l, &x);
update(1, 1, n, l, x);
}
if(op == 3){
scanf("%lld%lld", &l, &r);
printf("%lld\n", query(1, 1, n, l, r));
}
}
return 0;
}
```