努力做题
MorphLing
3月 01, 2021
XCPC 2021 Happy Winter Vacation
03.01
D. Ladder Game
https://acm.ecnu.edu.cn/contest/369/problem/D/
观察：把所有bar根据深度从上到下排序后遍历，每一个bar的作用相当于交换相邻两根柱子的编号，这样遍历一遍就可以得到最终的序列$\pi_L$。
总共有$h$根bar，h <= 50000，题解$O(h^2)$的做法正确性和复杂度都没看懂，从AC代码里找到一个$O(n^2 + h)$的做法。根据最终序列的顺序求出$before[x][y]$，$before[x][y]=1$表示$\pi_L$中x在y之前，否则x在y之后，然后再从上到下遍历一遍bar，只保留那些相对于最终状态不会改变两个序号相对位置的bar，也就是说如果左柱子编号为x，右柱子编号为y，只有当$before[x][y]=0$时才保留这根bar，否则直接删掉。
这个证明可以简化成另一个问题，已知一个序列$L1$，经过一系列相邻交换之后变成$L2$，问最多可以去掉多少个多余的相邻交换，使得最终结果不改变？
证明也很简单，假设最优解存在一个这种使得相对位置发生变化的交换，那么后面一定有一步要把它们两换回来，那只要把这两步同时去掉就得到一个更优解了，假设矛盾。
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << ' '
#define debugl(x) cerr << #x << " = " << x << '\n'
using namespace std;
typedef pair<int, int> pii;
const int N = 55, M = 1e3 + 5;
int n;
struct Bar {
int x, pos, idx;
bool operator < (Bar &B) {
if (pos != B.pos) return pos < B.pos;
else return x < B.x;
}
};
vector<Bar> B;
int line[N], before[N][N], tot;
vector<pii> ans;
int main() {
cin >> n;
for (int i = 1; i < n; i++) {
int p; scanf("%d", &p);
int idx = 0;
while(p) {
B.push_back({i, p, ++idx});
scanf("%d", &p);
}
}
sort(all(B));
for (int i = 1; i <= n; i++) line[i] = i;
for (auto &t : B) {
swap(line[t.x], line[t.x + 1]);
}
for (int i = 1; i <= n - 1; i++) {
for (int j = i + 1; j <= n; j++) {
before[line[i]][line[j]] = 1;
}
}
for (int i = 1; i <= n; i++) line[i] = i;
for (auto &t : B) {
if (!before[line[t.x]][line[t.x + 1]]) {
ans.push_back({t.x, t.idx});
swap(line[t.x], line[t.x + 1]);
}
}
cout << ans.size() << endl;
for (auto &t : ans) cout << t.first << ' ' << t.second << endl;
return 0;
}
03.02
H. Strike Zone
https://acm.ecnu.edu.cn/contest/369/problem/H/
比赛的时候陷入了一个误区，把问题完全转化成了一个2000*2000的矩阵上求最大子矩阵的问题，但是忽略了一共只有2000个点。
暴力枚举一维，比如说先枚举下边界，再往上推上边界，每往上推一行一定会多恰好一个点，然后把这个点的横坐标填上对应的权值，用线段树求出横坐标上最大子段和就可以了。
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << ' '
#define debugl(x) cerr << #x << " = " << x << '\n'
#define max3(a, b, c) (max(max((a), (b)), (c)))
using namespace std;
typedef pair<int, int> pii;
const int N = 2e3 + 5;
typedef long long ll;
struct Node {
int x, y, v;
}G[N];
vector<Node> Nodes;
vector<int> X, Y;
int n, n1, n2, idx, c1, c2;
ll ans;
map<int, int> dec_x, dec_y;
struct Segment_tree {
#define lson (o << 1)
#define rson (o << 1 | 1)
#define mid ((l + r) >> 1)
ll sum[N << 2], lsum[N << 2], rsum[N << 2], t[N << 2];
void pushup(int o) {
sum[o] = sum[lson] + sum[rson];
lsum[o] = max(lsum[lson], sum[lson] + lsum[rson]);
rsum[o] = max(rsum[rson], sum[rson] + rsum[lson]);
t[o] = max3(t[lson], t[rson], rsum[lson] + lsum[rson]);
}
void build(int o, int l, int r) {
if (l == r) {
sum[o] = lsum[o] = rsum[o] = t[o] = 0;
return;
}
build(lson, l, mid); build(rson, mid + 1, r);
pushup(o);
}
void modify(int o, int l, int r, int p, int v) {
if (l == r) {
sum[o] = v;
lsum[o] = rsum[o] = t[o] = max(0, v);
return;
}
if (p <= mid) modify(lson, l, mid, p, v);
else modify(rson, mid + 1, r, p, v);
pushup(o);
}
ll query() {
return t[1];
}
}seg;
int main() {
cin >> n1;
for (int i = 1; i <= n1; i++) {
int x, y; scanf("%d %d", &x, &y);
Nodes.push_back({x, y, 1});
X.push_back(x);
Y.push_back(y);
}
cin >> n2;
for (int i = 1; i <= n2; i++) {
int x, y; scanf("%d %d", &x, &y);
Nodes.push_back({x, y, -1});
X.push_back(x);
Y.push_back(y);
}
sort(all(X)), sort(all(Y));
idx = 0;
for (auto &t : X) dec_x[t] = ++idx;
idx = 0;
for (auto &t : Y) dec_y[t] = ++idx;
cin >> c1 >> c2;
for (auto &t : Nodes) {
int x = dec_x[t.x], y = dec_y[t.y], v = t.v == 1 ? c1 : -c2;
G[y] = {x, y, v};
}
n = n1 + n2;
for (int i = 1; i <= n; i++) {
seg.build(1, 1, n);
for (int j = i; j <= n; j++) {
seg.modify(1, 1, n, G[j].x, G[j].v);
ans = max(ans, seg.query());
}
}
cout << ans;
return 0;
}
03.03
J. Switches
http://codeforces.com/gym/102920/problem/J
题意：有n个灯和n个开关，每个灯对应多个开关，每个开关对应多个灯，按下某个开关会使得对应的灯亮暗情况发生变化。问对于每个灯k，是否存在一种开关方案，使得除了k之外的灯都暗，只有第k个灯亮。
把每个开关对应的灯号用二进制表示出来（如题目中输入的某一行），选择任意个开关后最终结果就是把所有行做异或之后的结果。题目也就是问用所有开关对应的数是否能异或出100..00 , 010..00 , 001..00 , … , 000..10 , 000..01每个数并输出方案，那么用异或线性基可以解决。唯一区别在于平时的异或线性基是在long long范围内的，但是这里二进制位数最多为500位，可以用类似于高精度的方法，用数组表示每个二进制，然后用循环实现异或。
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << ' '
#define debugl(x) cerr << #x << " = " << x << '\n'
#define rep(x,y,z) for (int x=y;x<=z;x++)
#define per(x,y,z) for (int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
const int N = 1e3 + 5;
int p[N][N], vis[N], x[N], n;
int vc[N][N];
void Insert(int idx) {
int tmp[N];
memset(tmp, 0, sizeof(tmp));
for (int i = n; i >= 1; i--) {
if (!x[i]) continue;
if (!vis[i]) {
for (int j = 1; j <= n; j++) {
vc[i][j] ^= tmp[j];
}
vis[i] = idx;
vc[i][vis[i]] ^= 1;
for (int j = 1; j <= n; j++)
p[i][j] = x[j];
return;
}
for (int j = 1; j <= n; j++) {
x[j] ^= p[i][j];
}
for (int j = 1; j <= n; j++) {
tmp[j] ^= vc[i][j];
}
}
}
int ans[N][N];
int ask(int num) {
for (int i = n; i >= 1; i--)
if (x[i]) {
for (int j = 1; j <= n; j++) x[j] ^= p[i][j];
for (int j = 1; j <= n; j++) {
ans[num][j] ^= vc[i][j];
}
}
for (int j = 1; j <= n; j++) {
if (x[j]) return 0;
}
return 1;
}
void fail() {
printf("-1\n");
exit(0);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = n; j >= 1; j--) {
scanf("%d", &x[j]);
}
Insert(i);
}
for (int i = 1; i <= n; i++) {
memset(x, 0, sizeof(x));
x[n - i + 1] = 1;
if (!ask(i)) fail();
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (ans[i][j]) printf("%d ", j);
}
printf("\n");
}
return 0;
}
A. Autonomous Vehicle
http://codeforces.com/gym/102920/problem/A
500个点，离散化之后最大在一个500*500的矩阵内，跑遍所有边的复杂度为$O(n^2)$，标记出所有的路口和终点，再预处理出每个点向上下左右移动一步的实际距离之后暴力模拟即可。通过观察可以发现路径一定会逆时针绕边上一周后回到起点，所以只要模拟一个周期就可以了。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << ' '
#define debugl(x) cerr << #x << " = " << x << '\n'
#define int long long
const int maxn = 1e6 + 5;
const int N = 1e3 + 5;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
ll p[maxn], p2[maxn];
ll n, d;
inline void read(int &x) {
char ch;
x = 0;
bool flag = false;
ch = getchar();
while(ch>'9' || ch < '0') {
if (ch =='-') flag = true;
ch = getchar();
}
while((ch <= '9' && ch >= '0')) {
x = x * 10 + ch - '0';
ch = getchar();
}
if (flag) x *= -1;
}
vector<int> X, Y;
int nn, t;
int m, idx;
map<int, int> mpx, mpy;
int dis[N][N][4];
bool road[N][N], inter[N][N], End[N][N];
struct Line {
int bx, by, ex, ey;
int type;
}l[N];
bool inside(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m;
}
struct status {
int x, y, dire, time;
};
map<int, status> record;
signed main()
{
read(nn); read(t);
for (int i = 1; i <= nn; i++) {
scanf("%lld %lld %lld %lld", &l[i].bx, &l[i].by, &l[i].ex, &l[i].ey);
if (l[i].bx == l[i].ex) l[i].type = 0;
else l[i].type = 1;
X.push_back(l[i].bx); X.push_back(l[i].ex);
Y.push_back(l[i].by); Y.push_back(l[i].ey);
}
sort(all(X)); sort(all(Y));
X.erase(unique(all(X)), X.end());
Y.erase(unique(all(Y)), Y.end());
idx = 0; for (auto &x : X) mpx[x] = ++idx;
idx = 0; for (auto &y : Y) mpy[y] = ++idx;
n = X.size(), m = Y.size();
for (int i = 1; i <= nn; i++) {
End[mpx[l[i].bx]][mpy[l[i].by]] = 1;
End[mpx[l[i].ex]][mpy[l[i].ey]] = 1;
if (l[i].type == 1) {
int dire = l[i].bx < l[i].ex;
if (!dire) dire = -1;
int y = mpy[l[i].by];
int pre = -1;
for (int x = mpx[l[i].bx]; pre != mpx[l[i].ex]; x += dire) {
pre = x;
if (road[x][y]) inter[x][y] = 1;
else road[x][y] = 1;
}
} else {
int dire = l[i].by < l[i].ey;
if (!dire) dire = -1;
int x = mpx[l[i].bx];
int pre = -1;
for (int y = mpy[l[i].by]; pre != mpy[l[i].ey]; y += dire) {
pre = y;
if (road[x][y]) inter[x][y] = 1;
else road[x][y] = 1;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k <= 3; k++) {
int nx = i + dx[k], ny = j + dy[k];
if (inside(nx, ny)) {
dis[i][j][k] = abs(X[nx - 1] - X[i - 1]) + abs(Y[ny - 1] - Y[j - 1]);
}
}
}
}
int stx = mpx[l[1].bx], sty = mpy[l[1].by];
int dire;
if (l[1].type == 0) {
if (l[1].by < l[1].ey) dire = 3;
else dire = 1;
} else {
if (l[1].bx < l[1].ex) dire = 0;
else dire = 2;
}
int nx = stx, ny = sty;
int tot = 0;
int nnx, nny;
status pre = {stx, sty, dire, 0};
do{
nnx = nx + dx[dire], nny = ny + dy[dire];
tot += dis[nx][ny][dire];
if (inter[nnx][nny]) dire -= 1;
if (End[nnx][nny]) dire -= 2;
if (dire < 0) dire += 4;
record[tot] = {nnx, nny, dire, tot};
nx = nnx, ny = nny;
}while(nnx != stx || nny != sty);
t = t % tot;
for (auto &x : record) {
status aaa = x.second;
if (aaa.time > t) {
int lft = t - pre.time;
int ansx = X[pre.x - 1] + dx[pre.dire] * lft;
int ansy = Y[pre.y - 1] + dy[pre.dire] * lft;
cout << ansx << ' ' << ansy << endl;
return 0;
}
pre = x.second;
}
return 0;
}
03.05
G. Same Color
dp。dp[i]表示只考虑排序后前i个点，使得前i个点满足条件最少要选的点数。那么在确定最后一个点选的位置后，考虑倒数第二个点可供选择的范围。
观察可知，任意两个选中的点之间要么颜色相同，要么只改变了一次颜色，第一种情况直接查询即可，第二种情况，假设选中的两个点分别为i, j，相邻的发生颜色变化的点为k, l，也就是顺序是i…kl…j，只要确保x[k]-x[i] <= x[j] - x[k]且x[j] - x[l] <= x[l] - x[i]，可以求出区间范围，线段树查询区间最小值就可以转移了。
又因为第一个选中的点之前必须颜色始终相同（最后一个同理），当i..n颜色相同时计算答案。
思路感觉没啥问题，但是代码一直过不了，不知道是不是数据有问题，改了两天也没过。不查了，思路对了就行。
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define debug(x) if (dbg) cerr << #x << " = " << x << ' '
#define debugl(x) if (dbg) cerr << #x << " = " << x << '\n'
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 5, INF = 0x3f3f3f3f, dbg = 0;
typedef long long ll;
int m, n, pre[N];
struct Node {
int x, c;
bool operator < (Node &N) {
return x < N.x;
}
}a[N];
inline void read(int &x) {
char ch;
x = 0;
bool flag = false;
ch = getchar();
while(ch > '9' || ch < '0') {
if (ch =='-') flag = true;
ch = getchar();
}
while(ch <= '9' && ch >= '0') {
x = x * 10 + ch - '0';
ch = getchar();
}
if (flag) x *= -1;
}
struct Segment_tree {
#define lson (o << 1)
#define rson (o << 1 | 1)
#define mid ((l + r) >> 1)
int mn[N << 2];
void pushup(int o) {
mn[o] = min(mn[lson], mn[rson]);
}
void modify(int o, int l, int r, int pos, int v) {
if (l == r) {
mn[o] = v;
return;
}
if (pos <= mid) modify(lson, l, mid, pos, v);
else modify(rson, mid + 1, r, pos, v);
pushup(o);
}
int query(int o, int l, int r, int L, int R) {
if (L > r || R < l || R < L) return INF;
if (L <= l && r <= R) return mn[o];
if (L > mid) return query(rson, mid + 1, r, L, R);
else if (R <= mid) return query(lson, l, mid, L, R);
else return min(query(lson, l, mid, L, R), query(rson, mid + 1, r, L, R));
}
}seg;
int dp[N], ans = INF, mnseq;
int getidx_L(int pos, int rb) {
int L = 1, R = rb;
while(R > L + 1) {
int MID = (L + R) >> 1;
if (a[MID].x >= pos) R = MID;
else L = MID + 1;
}
if (a[L].x >= pos) return L;
return R;
}
int getidx_R(int pos, int rb) {
int L = 1, R = rb;
while(R > L + 1) {
int MID = (L + R) >> 1;
if (a[MID].x <= pos) L = MID;
else R = MID - 1;
}
if (a[R].x <= pos) return R;
return L;
}
signed main() {
cin >> m >> n;
for (int i = 1; i <= n; i++) scanf("%d", &a[i].x); // read(a[i].x);
for (int i = 1; i <= n; i++) scanf("%d", &a[i].c); // read(a[i].c);
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
if (i == 1 || a[i].c != a[i - 1].c) pre[i] = i;
else pre[i] = pre[i - 1];
}
for (int i = 1; i <= n; i++) {
if (pre[i] == 1) {
dp[i] = 1;
if (pre[i] == pre[n]) ans = min(ans, dp[i]);
seg.modify(1, 1, n, i, dp[i]);
continue;
}
dp[i] = dp[i - 1] + 1;
dp[i] = min(dp[i], seg.query(1, 1, n, pre[i], i - 1) + 1);
int L, R;
L = max(getidx_L(a[pre[i] - 1].x - (a[i].x - a[pre[i] - 1].x), i), pre[pre[i] - 1]);
R = min(getidx_R(a[pre[i]].x - (a[i].x - a[pre[i]].x), i), pre[i] - 1);
dp[i] = min(dp[i], seg.query(1, 1, n, L, R) + 1);
if (pre[i] == pre[n]) ans = min(ans, dp[i]);
seg.modify(1, 1, n, i, dp[i]);
}
cout << ans << endl;
return 0;
}
0306
C. K-beautiful Strings
http://codeforces.com/contest/1493/problem/C
符合条件的字符串的模式是前缀与原字符串相同，某个位置字符比原来大，剩下的从小到大排。
所以只要枚举第一个比原字符串大的字符位置以及该位置上的字母就可以了。
判可行性的方法是，因为必须k个字符为一组一起拿，那么如果需要拿一个新的字符串，需要的长度就多k，对应的操作是tot += k，只要拿完前缀+第一个更大的字符后tot<=n，那么这种取法就是可行的。
需要注意n是输出的字符串长度，而不是原字符串长度。另外极限数据会爆int
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define mem(x, y) memset(x, y, sizeof(x))
#define debug(x) if (DEBUG) cerr << #x << " = " << x << ' ';
#define debugl(x) if (DEBUG) cerr << #x << " = " << x << '\n';
#define int long long
using namespace std;
typedef long long ll;
//const int DEBUG = 1;
const int DEBUG = 0;
const int N = 2e5 + 5, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
template<typename T>
inline void read(T &x) {
char ch;
x = 0;
bool flag = false;
ch = getchar();
while(ch > '9' || ch < '0') {
if (ch =='-') flag = true;
ch = getchar();
}
while(ch <= '9' && ch >= '0') {
x = x * 10 + ch - '0';
ch = getchar();
}
if (flag) x *= -1;
}
int T, n, k, len;
char s[N];
int cnt[30], ans, sum;
char ansone;
bool perfect() {
int sum = 0;
for (int i = 1; i <= n; i++) {
if (cnt[s[i] - 'a'] % k == 0) sum += k;
cnt[s[i] - 'a']++;
}
if (sum > n) return 0;
int tot = 0;
for (int i = 0; i < 26; i++) {
if (cnt[i]) cnt[i] = ((cnt[i] - 1) / k + 1) * k;
tot += cnt[i];
}
cnt[0] += n - tot;
for (int i = 1; i <= len; i++) {
printf("%c", s[i]);
cnt[s[i] - 'a']--;
}
for (int i = 0; i <= 25; i++) {
while (cnt[i]) {
printf("%c", i + 'a');
cnt[i]--;
}
}
printf("\n");
return 1;
}
signed main() {
cin >> T;
while(T--) {
scanf("%lld %lld\n", &n, &k);
scanf("%s", s + 1);
len = strlen(s + 1);
if (n % k != 0) {
printf("-1\n");
continue;
}
if (perfect()) continue;
ans = 0, sum = 0;
mem(cnt, 0);
for (int i = 1; i <= n; i++) {
char tc = s[i] - 'a' + 1;
for (char ra = s[i] + 1; ra <= 'z'; ra++) {
int tsum = sum;
if (cnt[ra - 'a'] % k == 0) tsum += k;
if (tsum <= n) {
ans = i, ansone = ra;
break;
}
}
if (cnt[s[i] - 'a'] % k == 0) sum += k;
cnt[s[i] - 'a']++;
}
if (ans == 0) {
printf("-1\n");
continue;
}
mem(cnt, 0);
for (int i = 1; i <= ans - 1; i++) {
printf("%c", s[i]);
cnt[s[i] - 'a']++;
}
printf("%c", ansone);
cnt[ansone - 'a']++;
int ttt = 0;
for (int i = 0; i < 26; i++) {
if (cnt[i]) cnt[i] = ((cnt[i] - 1) / k + 1) * k;
ttt += cnt[i];
}
cnt[0] += n - ttt;
for (int i = 1; i <= ans - 1; i++) {
cnt[s[i] - 'a']--;
}
cnt[ansone - 'a']--;
for (int i = 0; i < 26; i++) {
while (cnt[i]) {
printf("%c", i + 'a');
cnt[i]--;
}
}
printf("\n");
}
return 0;
}
D. GCD of an Array
均摊题。根据数据范围，每个数都可以拆成至多20个质数的乘积，用一个map[x][y]表示第x位置上第j个质数的个数，可以发现占用的空间是$O(n+q)$的
用$cnt[i]$记录第$i$个质数因子个数为0的位置个数（被消去的不算），那么就是当map[x][y]+=1且map[x][y]==0时，令cnt[y]—。每当cnt[y]被减成0时，说明每个位置都有第$y$个质数的因子了，那么统计答案，并从头到尾扫一遍重新计算$cnt[y]$，如果$cnt[y]$仍为0，就继续循环下去。
复杂度上可以发现，由于每个数至多拆成20个质数，也就是质数的数量也是$O(n+q)$的，一次消除操作时间为$O(n)$，但也至少需要$O(n)$个质数才能进行一次消除。所以均摊复杂度是$O(n+q)$，常数<=20。
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define mem(x, y) memset(x, y, sizeof(x))
#define debug(x) if (DEBUG) cerr << #x << " = " << x << ' ';
#define debugl(x) if (DEBUG) cerr << #x << " = " << x << '\n';
using namespace std;
typedef long long ll;
//const int DEBUG = 1;
const int DEBUG = 0;
const int N = 2e5 + 5, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
template<typename T>
inline void read(T &x) {
char ch;
x = 0;
bool flag = false;
ch = getchar();
while(ch > '9' || ch < '0') {
if (ch =='-') flag = true;
ch = getchar();
}
while(ch <= '9' && ch >= '0') {
x = x * 10 + ch - '0';
ch = getchar();
}
if (flag) x *= -1;
}
ll vis[N],prime[N],countPrime, pp[N];
void getPrime() {
for (int i=2;i<N;i++) {
if (!vis[i]) {
prime[++countPrime]=i;
pp[i] = countPrime;
}
for (int j=1;j<=countPrime;j++) {
if (i*prime[j]>=N) break;
vis[i*prime[j]]=1;
if (i%prime[j]==0) break;
}
}
}
map<int, int> b[N];
int tot[N], cnt[N];
int ans = 1;
int n, q;
void checkAgain(int j) {
cnt[j] = n;
for (int i = 1; i <= n; i++) {
b[i][j]--;
debugl(b[i][j]);
if (b[i][j] != 0) cnt[j]--;
}
}
int main() {
getPrime();
scanf("%d %d", &n, &q);
for (int i = 1; i < N; i++) cnt[i] = n;
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
for (int j = 1; prime[j] * prime[j] <= x; j++) {
if (x % prime[j] == 0) cnt[j]--;
while (x % prime[j] == 0) {
b[i][j]++;
x /= prime[j];
}
}
if (x != 1) {
int j = pp[x];
if (x % prime[j] == 0) cnt[j]--;
while (x % prime[j] == 0) {
b[i][j]++;
x /= prime[j];
}
}
}
for (int j = 1; j < N; j++) {
while (cnt[j] == 0) {
ans = 1ll * ans * prime[j] % MOD;
checkAgain(j);
}
}
for (int Q = 1; Q <= q; Q++) {
int i, y; scanf("%d %d", &i, &y);
for (int j = 1; prime[j] * prime[j] <= y; j++) {
if (y % prime[j] == 0) {
if (b[i][j] == 0) cnt[j]--;
while (y % prime[j] == 0) {
b[i][j]++;
y /= prime[j];
}
while (cnt[j] == 0) {
ans = 1ll * ans * prime[j] % MOD;
checkAgain(j);
}
}
}
if (y != 1) {
int j = pp[y];
if (y % prime[j] == 0) {
if (b[i][j] == 0) cnt[j]--;
while (y % prime[j] == 0) {
b[i][j]++;
y /= prime[j];
}
while (cnt[j] == 0) {
ans = 1ll * ans * prime[j] % MOD;
checkAgain(j);
}
}
}
printf("%d\n", ans);
}
return 0;
}