MnZn刚学OI一秒钟求助

#include<bits/stdc++.h>
#define int __int128
#define ll long long
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
	return x*f;
}
template <class T>
T randint(T l, T r = 0) 
{
    static mt19937 A(time(0));
    if(l>r)
        swap(l,r);
    uniform_int_distribution<T> B(l, r);
    return B(A);
}
int gcd(int x,int y)
{
	if(x<y)swap(x,y);
	while(y)
	{
		int t=x%y;
		x=y;
		y=t;
	}
	return x;
}
int qpow(int a,int n,int p)
{
	int ans=1;
	while(n)
	{
		if(n&1)ans=(ans*a)%p;
		a=a*a%p;
		n>>=1;
	}
	return ans;
}
bool Miller_Labin(int x)
{
	if(x<3)return x==2;
	if(x%2==0)return 0;
	int A[7]={2,325,9375,28178,450775,9780504,1795265022},d=x-1,r=0;
	while(d%2==0)d/=2,r++;
	for(int i=0;i<7;i++)
	{
		int a=A[i];
		int v=qpow(a,d,x);
		if(v<=1||v==x-1)continue;
		for(int j=1;j<=r;j++)
		{
			v=v*v%x;
			if(v==x-1&&j!=r)
			{
				v=1;
				break;
			}
			if(v==1)return 0;
		}
		if(v!=1)return 0;
	}
	return 1;
}
int Pollard_Rho(int N)
{
	if(N==4)return 2;
	if(Miller_Labin(N))return N;
	while(1)
	{
		int c=randint(1ll,(ll)(N-1));
        auto f=[=](ll x){return ((int)x*x+c)%N;};
		ll t=0,r=0,p=1,q;
		do
		{
			for(int i=0;i<128;i++)
            {
                t=f(t),r=f(f(r));
                if(t==r||(q=(int)p*abs(t-r)%N)==0)
                    break;
                p=q;
            }
            ll d=gcd(p,N);
            if(d>1)
                return d;
		}while(t!=r);
	}
}
const int mod=19260817;
vector<signed> vec;
set<int> factor;
vector<int> Factor;
vector<int> Vfactor[100005];
int a[100005];
struct node{
	signed id,l,r,Iwb;
	ll ans;
}Q[100005];
bool cmp(node x,node y)
{
	return x.Iwb<y.Iwb||(x.Iwb==y.Iwb&&(((x.Iwb%2==1)&&x.r<y.r)||((x.Iwb%2==0)&&x.r>y.r)));
}
bool cmp2(node x,node y)
{
	return x.id<y.id;
}
signed h[200005];
map<ll,signed> H;
ll inv[200005];
signed d[100005][169];
ll l=1,r=0,ans=1;
void add(signed x)
{
	for(signed i=0;i<Vfactor[x].size();i++)
	{
		if(h[Vfactor[x][i]]!=0)ans=(ans*inv[h[Vfactor[x][i]]])%mod;
		h[Vfactor[x][i]]++;
		if(h[Vfactor[x][i]]!=0)ans=ans*h[Vfactor[x][i]]%mod;
	}
}
void del(signed x)
{
	for(signed i=0;i<Vfactor[x].size();i++)
	{
		if(h[Vfactor[x][i]]!=0)ans=(ans*inv[h[Vfactor[x][i]]])%mod;
		h[Vfactor[x][i]]--;
		if(h[Vfactor[x][i]]!=0)ans=ans*h[Vfactor[x][i]]%mod;
	}
}
signed main()
{
//	freopen("sb.in","r",stdin);
	signed n=read(),m=read();
	signed block=sqrt(n);
	for(signed i=1;i<=1000;i++)
		if(Miller_Labin(i))
			vec.push_back(i);
	for(signed i=1;i<=n;i++)
	{
		a[i]=read();
		for(signed j=0;j<vec.size();j++)
		{
			while(a[i]%vec[j]==0)
			{
				a[i]/=vec[j];
				d[i][j+1]++;
			}
			d[i][j+1]+=d[i-1][j+1];
		}
		if(a[i]!=1)
		{
			int t=Pollard_Rho(a[i]);
			if(t==a[i])
			{
				factor.insert(a[i]);
				Vfactor[i].push_back(a[i]);
			}
			else
			{
				factor.insert(t);
				factor.insert(a[i]/t);
				Vfactor[i].push_back(t);
				Vfactor[i].push_back(a[i]/t);
			}
		}
	}
	for(signed i=1;i<=2*n;i++)inv[i]=qpow(i,mod-2,mod);
	for(signed i=1;i<=2*n;i++)h[i]=1;
	int cntccc=0;
	for(auto it=factor.begin();it!=factor.end();it++)
		H[*it]=++cntccc;
	for(signed i=1;i<=n;i++)
		for(signed j=0;j<Vfactor[i].size();j++)
			Vfactor[i][j]=H[Vfactor[i][j]];
	for(signed i=1;i<=m;i++)
	{
		signed l=read(),r=read();
		Q[i].id=i;
		Q[i].l=l;Q[i].r=r;
		Q[i].Iwb=(l-1)/block+1;
	}
	sort(Q+1,Q+m+1,cmp);
	for(signed i=1;i<=m;i++)
	{
		ll t=1;
		for(signed j=1;j<=168;j++)
			t=t*(d[Q[i].r][j]-d[Q[i].l-1][j]+1)%mod;
		while(r<Q[i].r)add(++r);
		while(l>Q[i].l)add(--l);
		while(l<Q[i].l)del(l++);
		while(r>Q[i].r)del(r--);
		Q[i].ans=ans*t%mod;
	}
	sort(Q+1,Q+m+1,cmp2);
	for(signed i=1;i<=m;i++)printf("%lld\n",Q[i].ans);
    return 0;
}