大意: 给定 n 元素序列, q 个操作: (1)区间乘 (2)单点除 (保证整除) (3) 区间求和对 m 取模
要求回答所有操作 (3) 的结果
主要是除法难办, 假设单点除 $x$, $x$ 中与 $m$ 互素的素因子可以直接费马小定理求逆, 其余因子维护一个向量即可.
这种沙茶题结果各种细节出错改了一个多小时...... 太菜了
- #include <iostream>
- #include <algorithm>
- #include <cstdio>
- #include <math.h>
- #include <set>
- #include <map>
- #include <queue>
- #include <string>
- #include <string.h>
- #define REP(i,a,n) for(int i=a;i<=n;++i)
- #define PER(i,a,n) for(int i=n;i>=a;--i)
- #define hr putchar(10)
- #define pb push_back
- #define lc (o<<1)
- #define rc (lc|1)
- #define mid ((l+r)>>1)
- #define ls lc,l,mid
- #define rs rc,mid+1,r
- #define x first
- #define y second
- #define io std::iOS::sync_with_stdio(false)
- #define endl '\n'
- using namespace std;
- typedef long long ll;
- typedef pair<int,int> pii;
- const int P = 1e9+7, INF = 0x3f3f3f3f;
- ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
- ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
- //head
- const int N = 1e5+10;
- int n, m, q, sz, Phi;
- vector<int> A;
- int phi(int x) {
- int s = x, mx = sqrt(x+0.5);
- REP(i,2,mx) if (x%i==0) {
- s = s/i*(i-1);
- A.pb(i);
- while (x%i==0) x/=i;
- }
- if (x>1) A.pb(x),s=s/x*(x-1);
- sz = A.size();
- return s;
- }
- ll qpow(ll a,ll n) {ll r=1%m;for (a%=m;n;a=a*a%m,n>>=1)if(n&1)r=r*a%m;return r;}
- int sum[N<<2], rtag[N<<2], tag[N<<2], res[N<<2];
- int c[N<<2][10], tagc[N<<2][10];
- int ans, ql, qr, qv[10];
- void pd(int o) {
- if (tag[o]!=1) {
- tag[lc] = (ll)tag[lc]*tag[o]%m;
- tag[rc] = (ll)tag[rc]*tag[o]%m;
- sum[lc] = (ll)sum[lc]*tag[o]%m;
- sum[rc] = (ll)sum[rc]*tag[o]%m;
- tag[o] = 1;
- }
- if (rtag[o]!=1) {
- res[lc] = (ll)res[lc]*rtag[o]%m;
- res[rc] = (ll)res[rc]*rtag[o]%m;
- rtag[lc] = (ll)rtag[lc]*rtag[o]%m;
- rtag[rc] = (ll)rtag[rc]*rtag[o]%m;
- rtag[o] = 1;
- }
- REP(i,0,sz-1) {
- c[lc][i]+=tagc[o][i],c[rc][i]+=tagc[o][i];
- tagc[lc][i]+=tagc[o][i],tagc[rc][i]+=tagc[o][i];
- tagc[o][i]=0;
- }
- }
- void pu(int o) {
- sum[o]=(sum[rc]+sum[lc])%m;
- }
- void build(int o, int l, int r) {
- sum[o]=res[o]=tag[o]=rtag[o]=1;
- if (l==r) {
- int t;
- scanf("%d", &t);
- sum[o] = t%m;
- REP(i,0,sz-1) {
- while (t%A[i]==0) t/=A[i],++c[o][i];
- }
- res[o] = t%m;
- return;
- }
- build(ls),build(rs);
- pu(o);
- }
- void mul(int o, int l, int r, int x, int R) {
- if (ql<=l&&r<=qr) {
- sum[o] = (ll)sum[o]*x%m;
- tag[o] = (ll)tag[o]*x%m;
- res[o] = (ll)res[o]*R%m;
- rtag[o] = (ll)rtag[o]*R%m;
- REP(i,0,sz-1) c[o][i]+=qv[i],tagc[o][i]+=qv[i];
- return;
- }
- pd(o);
- if (mid>=ql) mul(ls,x,R);
- if (mid<qr) mul(rs,x,R);
- pu(o);
- }
- void div(int o, int l, int r, int x, int v) {
- if (l==r) {
- REP(i,0,sz-1) {
- while (v%A[i]==0) v/=A[i],--c[o][i];
- }
- res[o] = (ll)res[o]*qpow(v,Phi-1)%m;
- sum[o] = res[o];
- REP(i,0,sz-1) sum[o]=(ll)sum[o]*qpow(A[i],c[o][i])%m;
- return;
- }
- pd(o);
- if (mid>=x) div(ls,x,v);
- else div(rs,x,v);
- pu(o);
- }
- void query(int o, int l, int r, int ql, int qr) {
- if (ql<=l&&r<=qr) return (ans+=sum[o])%=m,void();
- pd(o);
- if (mid>=ql) query(ls,ql,qr);
- if (mid<qr) query(rs,ql,qr);
- }
- int main() {
- scanf("%d%d", &n, &m);
- Phi = phi(m);
- build(1,1,n);
- scanf("%d", &q);
- while (q--) {
- int op, x, p;
- scanf("%d", &op);
- if (op==1) {
- scanf("%d%d%d",&ql,&qr,&x);
- int t = x;
- REP(i,0,sz-1) {
- qv[i] = 0;
- while (t%A[i]==0) t/=A[i],++qv[i];
- }
- mul(1,1,n,x,t);
- } else if (op==2) {
- scanf("%d%d",&p,&x);
- div(1,1,n,p,x);
- } else {
- scanf("%d%d",&ql,&qr);
- ans = 0, query(1,1,n,ql,qr);
- printf("%d\n", ans);
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2983216.html