题解 P4256 【公主の#19准备月考】

观察题面$,$需要维护区间$gcd$和$lcm.$ 值域是$[1,100],$ $[1,100]$范围内的$gcd$可以事先预处理出来然后可以$O(1)$查询$.$ $lcm$的话$,$就必须记录每个质因子的次数$.$ 不难发现$2^7=128>100,3^5=243>100,5^3=125>100,7^3=343>100,11^2=121>100$ 所以$,$ $2$ 和 $3$ 各自用 $3$ 个二进制位 $,$ $5$ 和 $7$ 各用 $2$ 个二进制位 $,$ 剩下的 $21$ 个质数各用 $1$ 个二进制位 $,$ 一共用 $31$ 个二进制位 $,$ 用一个 $int$ 存正好能存下$.$ 并且通过$O(1024^2)$预处理可以做到$O(1)$合并这个信息$.$ 处理完这些信息之后$,$直接上线段树就好了$.$ $O(1024^2+nlogn)$ ------- 又及$:$卡到$545ms$之后所有的优化都变成了负优化$...$那位$500ms$的神仙是怎么卡到的$?$能否赐教$,$在下感激不尽$!$ ----- 代码$:$ ```cpp #include <bits/stdc++.h> using namespace std; inline void read(int &x){ static char ch; x = 0,ch = getchar(); while (!isdigit(ch)) ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - '0',ch = getchar(); } inline int Getop(){ static char ch; ch = getchar(); while (!isalpha(ch)) ch = getchar(); return ((ch == 'L' || ch == 'G')) ? (ch == 'L' ? 1 : 2) : (ch == 'C' ? 3 : 4); } inline void write(int x){ if (x > 9) write(x/10); putchar(x%10+'0'); } const int N = 300001,p[] = {11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}; int d[101],Gcd[101][101],v[101],FF[1024][1024],num[1024]; inline int Get(int t,int p){ static int c; c = 0; while (!(t%p)) t/=p,++c; return c; } inline int power(int x,int y){ static int r; r = 1; while (y){ if (y&1) r*=x; x*=x,y>>=1; } return r; } inline void init(){ register int i,j; for (i = 1; i <= 100; ++i) for (j = 1; j <= i; ++j) if (!(i%j)) ++d[i]; for (i = 0; i <= 100; ++i) for (j = 0; j <= 100; ++j) Gcd[i][j] = __gcd(i,j); for (i = 1; i <= 100; ++i){ v[i] = Get(i,2) | (Get(i,3)<<3) | (Get(i,5)<<6) | (Get(i,7)<<8); for (j = 0; j < 21; ++j) if (!(i%p[j])){ v[i] |= 1<<10+j; break; } } for (i = 0; i < 1024; ++i) for (j = 0; j < 1024; ++j) FF[i][j] = max(i&7,j&7) | ((max(i&63,j&63)>>3)<<3) | ((max(i&255,j&255)>>6)<<6) | ((max(i,j)>>8)<<8); for (i = 0; i < 1024; ++i) num[i] = power(2,i&7) * power(3,(i&63)>>3) * power(5,(i&255)>>6) * power(7,i>>8); } inline int F(int x,int y){ return FF[x&1023][y&1023] + ((x|y)&2147482624); } inline int calc(int x,int mod){ static int r,i; //这个地方r应该开long long,但是为了卡常我暂时改成了int for (r = num[x&1023] % mod,x >>= 10,i = 0; i < 21 && x; ++i,x>>=1) if (x&1) r = r * p[i] % mod; return r; } int a[N],Gc[N<<2],Lc[N<<2],tag[N<<2]; #define up(o) Gc[o] = Gcd[Gc[o<<1]][Gc[o<<1|1]],Lc[o] = F(Lc[o<<1],Lc[o<<1|1]) #define Tag(o,x) tag[o] = Gc[o] = x,Lc[o] = v[x] #define down(o) if (tag[o]) Tag(o<<1,tag[o]),Tag(o<<1|1,tag[o]),tag[o] = 0 inline void Build(int o,int l,int r){ if (l == r){ Gc[o] = a[l],Lc[o] = v[a[l]]; return; } int mid = l+r>>1; Build(o<<1,l,mid); Build(o<<1|1,mid+1,r); up(o); } int ll,rr,vv; inline void Add(int o,int l,int r){ if (ll <= l && rr >= r){ Tag(o,vv); return; } down(o); int mid = l+r>>1; if (ll <= mid) Add(o<<1,l,mid); if (rr > mid) Add(o<<1|1,mid+1,r); up(o); } int qlcm; inline void Ask1(int o,int l,int r){ if (tag[o] || (ll <= l && rr >= r)){ qlcm = F(qlcm,Lc[o]); return; } int mid = l+r>>1; if (ll <= mid) Ask1(o<<1,l,mid); if (rr > mid) Ask1(o<<1|1,mid+1,r); } int qgcd; inline void Ask2(int o,int l,int r){ if (tag[o] || (ll <= l && rr >= r)){ qgcd = Gcd[qgcd][Gc[o]]; return; } int mid = l+r>>1; if (ll <= mid) Ask2(o<<1,l,mid); if (rr > mid) Ask2(o<<1|1,mid+1,r); } int n,q; int main(){ int i,op,mod,ans; init(),read(n),read(q); for (i = 1; i <= n; ++i) read(a[i]); Build(1,1,n); while (q--){ op = Getop(),read(ll),read(rr); if (op == 3){ read(vv),Add(1,1,n); continue; } read(mod); if (op == 1) qlcm = 0,Ask1(1,1,n),ans = calc(qlcm,mod); else qgcd = 0,Ask2(1,1,n),ans = (op == 2 ? qgcd : d[qgcd]) % mod; write(ans),putchar('\n'); } return 0; } ```