Description：

求区间积的欧拉函数。

$1\leqslant n\leqslant 2\times 10^5,1\leqslant a_i\leqslant 10^6$

Solution1：

值域分块，小于等于 $1000$ 的质数只有 $168$ 个，可以用线段树 $+bitset$ 暴力维护，然后对于每个询问乘一个 $\frac{p-1}p$ ，大于 $1000$ 的质因子每个数只有一个，因此单次插入一个数是 $O(1)$ 的，可以用莫队，复杂度 $O(n\sqrt n)$ 。

Code1：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<bitset>

#include<cctype>

#include<cstring>

using namespace std;

int n,p;

#define MAXN 200010

#define P 998244353

#define I inline

#define re register

I int rd()

{

	re int res = 0;re char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res;

}

I int power(int a,int b)

{

	re int res = 1;

	for(;b > 0;a = 1ll * a * a % P,b = b >> 1)if(b & 1)res = 1ll * res * a % P;

	return res;

}

I int inver(int a){return power(a,P - 2);}

int a[MAXN];

int ans[MAXN];

int s[MAXN];

#define N 1000000

int prime[N + 5],bel[N + 5],tot = 0,mindiv[N + 5],inv[MAXN];

int inv1[MAXN],inv2[MAXN];

bool isprime[N + 5];

int mxpr[MAXN];

struct query

{

	int l,r,id;

}q[MAXN];

int sum[MAXN];

I int calc(int p,int c)

{

	if(c == 0)return 1;

	return 1ll * power(p,c - 1) * (p - 1) % P;

}

int blo,pos[MAXN];

bool cmp_pos(query a,query b)

{

	if(pos[a.l] != pos[b.l])return pos[a.l] < pos[b.l];

	else if(pos[a.l] & 1)return a.r < b.r;

	else return a.r > b.r;

}

int curphi = 1;

int cnt[N + 5];

I void add(int v)

{

	if(v == 0)return;

	if(cnt[v] == 0)curphi = 1ll * curphi * (v - 1) % P;

	else curphi = 1ll * curphi * v % P;

	++cnt[v];

	return;

}

I void del(int v)

{

	if(v == 0)return;

	--cnt[v];

	if(cnt[v] == 0)curphi = 1ll * curphi * inv2[bel[v]] % P;

	else curphi = 1ll * curphi * inv1[bel[v]] % P;

	return;

}

bitset<180> ss[MAXN];

struct node

{

	int lc,rc;

	bitset<180> s;

	int val;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)

	{

		t[rt].s = ss[l];

		if(mxpr[l])t[rt].val = a[l] / mxpr[l];

		else t[rt].val = a[l];

		return;

	}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	t[rt].val = 1ll * t[t[rt].lc].val * t[t[rt].rc].val % P;

	t[rt].s = t[t[rt].lc].s | t[t[rt].rc].s;

	return;

}

int queryv(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].val;

	if(R <= mid)return queryv(t[rt].lc,L,R,l,mid);

	if(L > mid)return queryv(t[rt].rc,L,R,mid + 1,r);

	return 1ll * queryv(t[rt].lc,L,R,l,mid) * queryv(t[rt].rc,L,R,mid + 1,r) % P;

}

bitset<180> queryb(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].s;

	if(R <= mid)return queryb(t[rt].lc,L,R,l,mid);

	if(L > mid)return queryb(t[rt].rc,L,R,mid + 1,r);

	return queryb(t[rt].lc,L,R,l,mid) | queryb(t[rt].rc,L,R,mid + 1,r);

}

int main()

{

	n = rd();

	re int mx = 0;

	for(re int i = 1;i <= n;++i)mx = max(a[i] = rd(),mx);

	for(re int i = 2;i <= mx;++i)isprime[i] = true;

	for(re int i = 2;i <= mx;++i)

	{

		if(isprime[i])prime[++tot] = i,bel[i] = tot,mindiv[i] = i;

		for(re int j = 1;j <= tot && i * prime[j] <= mx;++j)

		{

			isprime[i * prime[j]] = false;mindiv[i * prime[j]] = prime[j];

			if(i % prime[j] == 0)break;

		}

	}

	int mv = 0;

	for(re int i = 1;i <= n;++i)

	{

		re int s = a[i];

		while(s != 0 && s != 1)

		{

			if(mindiv[s] > 1000)mxpr[i] = mindiv[s],s /= mindiv[s];

			else

			{

				re int cnt = 0,v = mindiv[s];

				while(s % v == 0)s /= v,++cnt;

				ss[i][bel[v]] = true;

				mv = max(mv,bel[v]);

			}

		}

	}

	build(root,1,n);

	p = rd();

	for(re int k = 1;k <= mv;++k)inv[k] = 1ll * inver(prime[k]) * (prime[k] - 1) % P;

	for(re int k = 1;k <= tot;++k)inv1[k] = inver(prime[k]),inv2[k] = inver(prime[k] - 1);

	for(re int i = 1;i <= p;++i)

	{

		q[i].id = i;q[i].l = rd();q[i].r = rd();

		ans[i] = queryv(root,q[i].l,q[i].r,1,n);

		re bitset<180> s = queryb(root,q[i].l,q[i].r,1,n);

		for(re int k = 1;k <= mv;++k)if(s[k])ans[i] = 1ll * ans[i] * inv[k] % P;

	}

	blo = sqrt(n);

	for(re int i = 1;i <= n;++i)pos[i] = (i - 1) / blo + 1;

	sort(q + 1,q + 1 + p,cmp_pos);

	for(re int i = 1,l = 1,r = 0;i <= p;++i)

	{

		while(r < q[i].r)add(mxpr[++r]);

		while(l > q[i].l)add(mxpr[--l]);

		while(r > q[i].r)del(mxpr[r]),--r;

		while(l < q[i].l)del(mxpr[l]),++l;

		ans[q[i].id] = 1ll * ans[q[i].id] * curphi % P;

	}

	for(re int i = 1;i <= p;++i)printf("%d\n",ans[i]);

	return 0;

}

Solution2：

如果强制在线的话，可以用主席树，让每个数只在最靠右的位置贡献 $\frac{p-1}p$ ，于是插入就是在上一个位置除一个 $\frac p{p-1}$ ，在这个位置乘一个 $p-1$ 。

Code2：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<bitset>

#include<cctype>

#include<cstring>

using namespace std;

int n,p;

#define MAXN 200010

#define P 998244353

#define I inline

#define re register

I int rd()

{

	re int res = 0;re char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res;

}

I int power(int a,int b)

{

	re int res = 1;

	for(;b > 0;a = 1ll * a * a % P,b = b >> 1)if(b & 1)res = 1ll * res * a % P;

	return res;

}

I int inver(int a){return power(a,P - 2);}

int a[MAXN];

int ans[MAXN];

int s[MAXN];

#define N 1000000

int prime[N + 5],bel[N + 5],tot = 0,mindiv[N + 5],inv[MAXN];

bool isprime[N + 5];

int mxpr[MAXN];

I int calc(int p,int c)

{

	if(c == 0)return 1;

	return 1ll * power(p,c - 1) * (p - 1) % P;

}

namespace ST

{ 

	bitset<180> ss[MAXN];

	struct node

	{

		int lc,rc;

		bitset<180> s;

		int val;

	}t[MAXN << 1];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root;

	#define mid ((l + r) >> 1)

	void build(int &rt,int l,int r)

	{

		rt = newnode();

		if(l == r)

		{

			t[rt].s = ss[l];

			if(mxpr[l])t[rt].val = a[l] / mxpr[l];

			else t[rt].val = a[l];

			return;

		}

		build(t[rt].lc,l,mid);

		build(t[rt].rc,mid + 1,r);

		t[rt].val = 1ll * t[t[rt].lc].val * t[t[rt].rc].val % P;

		t[rt].s = t[t[rt].lc].s | t[t[rt].rc].s;

		return;

	}

	int queryv(int rt,int L,int R,int l,int r)

	{

		if(L <= l && r <= R)return t[rt].val;

		if(R <= mid)return queryv(t[rt].lc,L,R,l,mid);

		if(L > mid)return queryv(t[rt].rc,L,R,mid + 1,r);

		return 1ll * queryv(t[rt].lc,L,R,l,mid) * queryv(t[rt].rc,L,R,mid + 1,r) % P;

	}

	bitset<180> queryb(int rt,int L,int R,int l,int r)

	{

		if(L <= l && r <= R)return t[rt].s;

		if(R <= mid)return queryb(t[rt].lc,L,R,l,mid);

		if(L > mid)return queryb(t[rt].rc,L,R,mid + 1,r);

		return queryb(t[rt].lc,L,R,l,mid) | queryb(t[rt].rc,L,R,mid + 1,r);

	}

}

namespace FT

{

	struct node

	{

		int lc,rc;

		int val;

	}t[MAXN * 30];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root[MAXN];

	int last[N + 5];

	void build(int &rt,int l,int r)

	{

		rt = newnode();t[rt].val = 1;

		if(l == r)return;

		build(t[rt].lc,l,mid);

		build(t[rt].rc,mid + 1,r);

		return;

	}

	void insert(int &rt,int p,int v,int l,int r)

	{

		int k = newnode();t[k] = t[rt];rt = k;

		if(l == r){t[rt].val = 1ll * t[rt].val * v % P;return;}

		if(p <= mid)insert(t[rt].lc,p,v,l,mid);

		else insert(t[rt].rc,p,v,mid + 1,r);

		t[rt].val = 1ll * t[t[rt].lc].val * t[t[rt].rc].val % P;

		return;

	}

	int query(int rt,int L,int R,int l,int r)

	{

		if(L <= l && r <= R)return t[rt].val;

		if(R <= mid)return query(t[rt].lc,L,R,l,mid);

		if(L > mid)return query(t[rt].rc,L,R,mid + 1,r);

		return 1ll * query(t[rt].lc,L,R,l,mid) * query(t[rt].rc,L,R,mid + 1,r) % P;

	}

}

int main()

{

	n = rd();

	re int mx = 0;

	for(re int i = 1;i <= n;++i)mx = max(a[i] = rd(),mx);

	for(re int i = 2;i <= mx;++i)isprime[i] = true;

	for(re int i = 2;i <= mx;++i)

	{

		if(isprime[i])prime[++tot] = i,bel[i] = tot,mindiv[i] = i;

		for(re int j = 1;j <= tot && i * prime[j] <= mx;++j)

		{

			isprime[i * prime[j]] = false;mindiv[i * prime[j]] = prime[j];

			if(i % prime[j] == 0)break;

		}

	}

	int mv = 0;

	for(re int i = 1;i <= n;++i)

	{

		re int s = a[i];

		while(s != 0 && s != 1)

		{

			if(mindiv[s] > 1000)mxpr[i] = mindiv[s],s /= mindiv[s];

			else

			{

				re int cnt = 0,v = mindiv[s];while(s % v == 0)s /= v,++cnt;

				ST::ss[i][bel[v]] = true;mv = max(mv,bel[v]);

			}

		}

	}

	ST::build(ST::root,1,n);

	p = rd();

	for(re int k = 1;k <= mv;++k)inv[k] = 1ll * inver(prime[k]) * (prime[k] - 1) % P;

	FT::build(FT::root[0],1,n);

	for(re int i = 1;i <= n;++i)

	{

		FT::root[i] = FT::root[i - 1];

		if(!mxpr[i])continue;

		if(FT::last[mxpr[i]] != 0)FT::insert(FT::root[i],FT::last[mxpr[i]],1ll * mxpr[i] * inver(mxpr[i] - 1) % P,1,n);

		FT::insert(FT::root[i],i,mxpr[i] - 1,1,n);

		FT::last[mxpr[i]] = i;

	}

	int l,r;

	for(re int i = 1;i <= p;++i)

	{

		l = rd();r = rd();

		ans[i] = ST::queryv(ST::root,l,r,1,n);

		re bitset<180> s = ST::queryb(ST::root,l,r,1,n);

		for(re int k = 1;k <= mv;++k)if(s[k])ans[i] = 1ll * ans[i] * inv[k] % P;//cout << ans[i] << endl;

		ans[i] = 1ll * ans[i] * FT::query(FT::root[r],l,r,1,n) % P;

		printf("%d\n",ans[i]);

	}

	return 0;

}