1732E - Location - CodeForces Solution

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define ll long long
#define vi vector < int >
using namespace std;
const int N = 1 << 17, T = 5e4;
int n, q, tb[N];
unsigned int a[N], b[N], c[N], f[N];
vi vc[N];
bool pr[N];
unsigned int Inv(unsigned int x) {
unsigned int w = 1;
L(t, 0, 31) if((w * x - 1) & ((1LL << (t + 1)) - 1)) w += 1u << t;
return w;
}
unsigned int iv[N];
int main() {
//	freopen("data.in", "r", stdin);
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
L(i, 2, T) if(!vc[i].size()) for(int j = i; j <= T; j += i) vc[j].emplace_back(i);
L(i, 1, T)
if(i & 1) iv[i] = Inv(i), iv[i] *= iv[i];
else iv[i] = iv[i >> 1];
cin >> n >> q ;
L(i, 1, n) cin >> a[i];
L(i, 1, n) cin >> b[i];
L(i, 1, n)
c[i] = (a[i] >> __builtin_ctz(a[i] | b[i])) * iv[__gcd(a[i], b[i])],
a[i] = __builtin_ctz(a[i] | b[i]), tb[i] = __builtin_ctz(b[i]);
while(q--) {
int t, l, r, x;
cin >> t >> l >> r;
if(t == 1) {
cin >> x;
int prd = 1;
f[1] = x;
for(const int &u : vc[x]) {
int xp = 1;
while(x % ((ll) prd * u) == 0) {
for(int blk = 1; blk <= u; blk <<= 1)
memcpy(f + blk * prd + 1, f + 1,
sizeof(unsigned int) * min(u - blk, blk) * prd);
xp *= u, prd *= u;
if(u != 2) for(int i = xp; i <= prd; i += xp) f[i] *= iv[u];
else for(int i = xp; i <= prd; i += xp) f[i] >>= 1;
}
}
L(i, prd + 1, T) f[i] = f[i - prd];
L(i, l, r) c[i] = f[b[i]];
int w = __builtin_ctz(x);
L(i, l, r) a[i] = min(tb[i], w);
} else {
unsigned int ns = -1;
L(i, l, r) ns = min(ns, b[i] * c[i] >> a[i]);
cout << ns << '\n';
}
}
return 0;
}