显示代码纯文本
#include <map>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef signed long long TYPE;
typedef std::map<TYPE,TYPE> SSMP;
typedef std::vector<TYPE> VCINT;
typedef SSMP::iterator SSIT;
const TYPE MOD=(TYPE)1E9+7;
const TYPE MOS=300010;
const TYPE MAXN=MOS;
TYPE cnk=0,cns=0;
TYPE prime[MOS];
TYPE last[MOS];
TYPE ans[MOS];
TYPE mpt[MOS];
bool vis[MOS];
void fin(TYPE&k){
static int c;
do{c=getchar();}while(c<'0'||c>'9');
do{k=k*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
}
TYPE gcd(TYPE a,TYPE b){
return !b ? a:gcd(b,a%b);
}
TYPE GCD(TYPE a,TYPE b){
if(a==0)return b;
if(b==0)return a;
return gcd(a,b);
}
struct ASKER{
TYPE l,r,id;
ASKER(TYPE a=0,TYPE b=0,TYPE c=0)
:l(a),r(b),id(c){}
bool operator <(const ASKER&a)
const {return r<a.r;}
}ask[MOS];
struct MUM{
TYPE id,last,val,num;
MUM(TYPE a=0,TYPE b=0,TYPE c=0,TYPE d=0)
:id(a),last(b),val(c),num(d){}
}AT[MOS<<5];
void get_prime(TYPE N)
{
TYPE cnt=0;
for(TYPE i=2; i<=N; ++i)
{
if(!vis[i])prime[++cnt]=i;
for(TYPE j=1; j<=cnt&&prime[j]*i<=N; ++j)
{
vis[prime[j]*i]=true;
if(i%prime[j]==0)break;
}
}//printf("ztc's prime:%d\n",cnt);
}
void SET(TYPE x,TYPE idx)
{
TYPE temp=0;
const TYPE maxp=sqrt(x);
for(TYPE i=1; prime[i]<=maxp; ++i)
{
if(x%prime[i]==0)
{
temp=1;
while(x%prime[i]==0)
{
x/=prime[i];
temp*=prime[i];
if(mpt[temp]==0)
mpt[temp]=++cnk;
AT[++cns]=MUM(idx,0,prime[i],temp);
}
}
}
if(x>1){
temp=x;
if(mpt[temp]==0)
mpt[temp]=++cnk;
AT[++cns]=MUM(idx,0,x,temp);
}return ;
}
TYPE pow(TYPE a,TYPE p)
{
TYPE ans=1;
while(p)
{
if(p&1)ans=ans*a%MOD;
a=a*a%MOD;
p>>=1;
}
return ans;
}
TYPE inv(TYPE a){
return pow(a,MOD-2);
}
struct FFT{
TYPE c[MAXN],N;
void init(TYPE NN){N=NN;
for(TYPE i=1;i<=N;++i)
c[i]=1LL;
}
void change(TYPE pos,TYPE val){
if(pos==0)return;
// printf("pos:%lld %lld\n",pos,val);
for(;pos<=N;pos+=pos&-pos)
c[pos]=c[pos]*val%MOD;
}TYPE ask(TYPE pos){
TYPE ans=1;
for(;pos;pos-=pos&-pos)
ans=ans*c[pos]%MOD;
return ans;
}
}ft;
void prep(TYPE N,TYPE Q){
ft.init(N);
for(TYPE i=1;i<=cns;++i){
AT[i].last=last[AT[i].num];
// printf("::%lld %lld\n",AT[i].last,AT[i].num);
last[AT[i].num]=AT[i].id;
}std::sort(ask+1,ask+Q+1);
}
SSMP SET(TYPE x)
{
SSMP ans;
TYPE cnt=0;
const TYPE maxp=sqrt(x);
for(TYPE i=1; prime[i]<=maxp; ++i)
{
if(x%prime[i]==0)
{
cnt=0;
while(x%prime[i]==0)
{
x/=prime[i];
++cnt;
}
ans[prime[i]]=cnt;
}
}
if(x>1)ans[x]=1;
// SHOW(ans);
return ans;
}
SSMP UNION(SSMP&a,SSMP&b)
{
SSMP ans;
// SHOW(a);SHOW(b);
SSIT itp=a.begin(),ito=a.end();
SSIT itq=b.begin(),itu=b.end();
while(itp!=ito||itq!=itu)
{
if(itp==ito)
{
ans[itq->first]=itq->second;
++itq;
}
else if(itq==itu)
{
ans[itp->first]=itp->second;
++itp;
}
else
{
if((itp->first)>(itq->first))
{
ans[itq->first]=itq->second;
++itq;
}
else if((itp->first)<(itq->first))
{
ans[itp->first]=itp->second;
++itp;
}
else
{
ans[itp->first]=std::max((itp->second),(itq->second));
++itp;
++itq;
}
}
}//SHOW(ans);printf("%d",rewrite(ans));
return ans;
}
TYPE rewrite(SSMP t)
{
SSIT itp=t.begin(),ito=t.end();
TYPE ans=1;
while(itp!=ito)
{
//printf("f:%d s:%d\n",itp->first,itp->second);
ans=ans*pow(itp->first,itp->second)%MOD;
++itp;
}//printf("ans::%d %d\n",ans,t.size());
return ans;
}
struct ZKW{
TYPE ma[MAXN<<2];
TYPE len;
void init(VCINT&f,TYPE N){
for(len=1;len<=N+1;len<<=1);
for(TYPE i=len+1;i<=len+N;++i)ma[i]=f[i-len];f.clear();
for(TYPE i=len-1;i>=1;--i)ma[i]=GCD(ma[i<<1],ma[i<<1|1]);
}
TYPE ask(TYPE l,TYPE r){
TYPE ans=0;
for(l+=len-1,r+=len+1;l^r^1;l>>=1,r>>=1){
if(~l&1)ans=GCD(ans,ma[l^1]);
if( r&1)ans=GCD(ans,ma[r^1]);
}
return ans;
}
}st;
VCINT w;
main()
{
freopen("Keller_T233.in","r",stdin);
freopen("Keller_T233.out","w",stdout);
get_prime(50000);
TYPE N,Q,x,y,j=1,k=1;
w.push_back(0);
scanf("%lld%lld",&N,&Q);
for(TYPE i=1;i<=N;++i){
scanf("%lld",&x);
SET(x,i);w.push_back(x);
}st.init(w,N);
for(TYPE i=1;i<=Q;++i){
scanf("%lld%lld",&x,&y);
ask[i]=ASKER(x,y,i);
}prep(N,Q);
for(TYPE i=1;i<=N;++i){
while(j<=cns&&AT[j].id==i){
ft.change(i,AT[j].val);
ft.change(AT[j].last,inv(AT[j].val));
++j;
}
while(k<=Q&&ask[k].r==i){
ans[ask[k].id]=ft.ask(ask[k].r)
*inv(ft.ask(ask[k].l-1))%MOD
*st.ask(ask[k].l,ask[k].r)%MOD;
++k;
}
}for(TYPE i=1;i<=Q;++i){
printf("%lld\n",ans[i]);
}while(getchar()!=EOF);
return 0;
}
YGOI_真神名曰驴蛋蛋