number⋅x+product⋅y=1 有整数x，y解的条件是gcd(number, product) == 1.
product用线段树维护一下，然后现学了个欧拉函数。
可以这样假如x = p1^a1 * p2^a2 * p3^a3 * ... * pn^an，那么phi(x) = (p1 - 1) * p1^(a1 - 1) + (p2 - 1) * p2^(a2 - 1) + (p3 - 1) * p3^(a3 - 1) + ... + (pn - 1) * pn^(an - 1).
速度奇慢，明早优化。。。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define drep(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define mp make_pair
#define pb push_back
#define clr(x) memset(x, 0, sizeof(x))
#define xx first
#define yy second
int pri[] = { , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , }; const int maxn = , mod = ;
int cnt[maxn << ][];
void Push_up(int o) { rep(i, , ) cnt[o][i] = cnt[o << ][i] + cnt[o << | ][i]; }
void fac(int o, int v) {
rep(i, , ) cnt[o][i] = ;
while (v != ) {
for (int i = ; i <= && v != ; i++)
while (v != && v % pri[i] == ) cnt[o][i]++, v /= pri[i];
}
}
void update(int o, int l, int r, int x, int v) {
if (l == r) {
fac(o, v);
return;
}
int mid = l + r >> ;
if (x <= mid) update(o << , l, mid, x, v);
else update(o << | , mid + , r, x, v);
Push_up(o);
}
int ret[];
void query(int o, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
rep(i, , ) ret[i] += cnt[o][i];
return;
}
int mid = l + r >> ;
if (ql <= mid) query(o << , l, mid, ql, qr);
if (qr > mid) query(o << | , mid + , r, ql, qr);
}
int POW(int base, int num) {
long long ha = ;
long long b = base;
while (num) {
if (num & ) ha *= b, ha %= mod;
b *= b;
b %= mod;
num >>= ;
}
return ha;
}
int main() {
int n; scanf("%d", &n);
rep(i, , ) update(, , , i, );
while (n--) {
int op, x, y; scanf("%d%d%d", &op, &x, &y);
if (op == ) update(, , , x, y);
else {
memset(ret, , sizeof(ret));
query(, , , x, y);
long long ans = ;
rep(i, , ) {
if (!ret[i]) continue;
ans *= POW(pri[i], ret[i] - );
ans %= mod;
ans *= pri[i] - ;
ans %= mod;
}
printf("%lld\n", ans);
}
}
}