http://www.tsinsen.com/ViewGProblem.page?gpid=A1339
题解：https://blog.csdn.net/LOI_DQS/article/details/51251737
对着题解A掉了。。。然而并不知道为什么要这么转化问题。。。
复杂度nlog^2n级别吧
1 #include<cstdio> 2 #include<algorithm> 3 #include<map> 4 #include<cmath> 5 #define fi first 6 #define se second 7 #define md 1000000007 8 using namespace std; 9 typedef long long LL; 10 typedef pair<int,int> P; 11 int a[1700100],d[1700100],nxt[1700100],pos[100100],len; 12 bool vis[50100]; 13 int prime[20100]; 14 bool fir[1700100]; 15 void dprime(int x,map<int,int> &ma) 16 { 17 ma.clear(); 18 if(x<=1) return; 19 int i,end=floor(sqrt(x+0.5)); 20 for(i=1;prime[i]<=end;i++) 21 while(x!=prime[i]) 22 { 23 if(x%prime[i]==0) 24 { 25 ma[prime[i]]++; 26 x/=prime[i]; 27 } 28 else 29 break; 30 } 31 ma[x]++; 32 } 33 int n,qq; 34 namespace S 35 { 36 #define mid (l+((r-l)>>1)) 37 #define lc (num<<1) 38 #define rc (num<<1|1) 39 int dat[40000000]; 40 void build(int l,int r,int num) 41 { 42 if(l==r){dat[num]=fir[l]?d[l]:1;return;} 43 build(l,mid,lc);build(mid+1,r,rc); 44 dat[num]=LL(dat[lc])*dat[rc]%md; 45 } 46 int L,R,x; 47 void upd(int l,int r,int num) 48 { 49 if(l==r) {dat[num]=x;return;} 50 if(L<=mid) upd(l,mid,lc); 51 else upd(mid+1,r,rc); 52 dat[num]=LL(dat[lc])*dat[rc]%md; 53 } 54 int que(int l,int r,int num) 55 { 56 if(L<=l&&r<=R) return dat[num]; 57 int ans=1; 58 if(L<=mid) ans=LL(ans)*que(l,mid,lc)%md; 59 if(mid<R) ans=LL(ans)*que(mid+1,r,rc)%md; 60 return ans; 61 } 62 #undef mid 63 #undef lc 64 #undef rc 65 } 66 int poww(int a,int b) 67 { 68 LL ans=1,base=a; 69 for(;b;base=base*base%md,b>>=1) 70 if(b&1) 71 ans=ans*base%md; 72 return ans; 73 } 74 struct Q 75 { 76 int l,r,num,ans; 77 }q[100100]; 78 bool operator<(const Q &a,const Q &b) {return a.l<b.l||(a.l==b.l&&a.r<b.r);} 79 bool cmp(const Q &a,const Q &b) {return a.num<b.num;} 80 int main() 81 { 82 int i,j,t;map<int,int> tans; 83 map<int,int>::iterator it; 84 for(i=2;i<=50000;i++) 85 { 86 if(!vis[i]) prime[++prime[0]]=i; 87 for(j=1;j<=prime[0]&&i*prime[j]<=50000;j++) 88 { 89 vis[i*prime[j]]=1; 90 if(i%prime[j]==0) break; 91 } 92 } 93 scanf("%d%d",&n,&qq); 94 for(i=1;i<=n;i++) 95 { 96 scanf("%d",&t);dprime(t,tans); 97 for(it=tans.begin();it!=tans.end();it++) 98 for(j=1;j<=it->second;j++) 99 ++len,a[len]=poww(it->first,j),d[len]=it->first; 100 pos[i]=len; 101 } 102 tans.clear(); 103 for(i=1;i<=len;i++) 104 { 105 if(!tans[a[i]]) fir[i]=1; 106 else nxt[tans[a[i]]]=i; 107 tans[a[i]]=i; 108 } 109 S::build(1,len,1); 110 for(i=1;i<=qq;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].num=i,q[i].l=pos[q[i].l-1]+1,q[i].r=pos[q[i].r]; 111 sort(q+1,q+qq+1); 112 for(i=1,j=1;i<=qq;i++) 113 { 114 for(;j<q[i].l;) 115 { 116 if(nxt[j]) 117 { 118 S::L=nxt[j];S::x=d[nxt[j]];S::upd(1,len,1); 119 } 120 ++j; 121 } 122 S::L=q[i].l;S::R=q[i].r; 123 q[i].ans=S::que(1,len,1); 124 } 125 sort(q+1,q+qq+1,cmp); 126 for(i=1;i<=qq;i++) printf("%d ",q[i].ans); 127 return 0; 128 }