【51 Nod 1203】JZPLCM

2019-11-11 02:38:43

字體：大中小

供稿：網(wǎng)友

Description

長度為N的正整數(shù)序列S，有Q次詢問，每次詢問一段區(qū)間內(nèi)所有數(shù)的lcm(即最小公倍數(shù))。由于答案可能很大，輸出答案Mod 10^9 + 7。例如：2 3 4 5，詢問[1,3]區(qū)間的最小公倍數(shù)為2 3 4的最小公倍數(shù) = 12。

Solution

一段數(shù)的最小公倍數(shù)中每個(gè)質(zhì)數(shù)的指數(shù)就是這段數(shù)的這個(gè)質(zhì)數(shù)出現(xiàn)的最大次數(shù)。那么現(xiàn)在的問題就是怎么去維護(hù)一個(gè)質(zhì)數(shù)的最大出現(xiàn)次數(shù)。有很多組詢問，我們考慮離線，把左端點(diǎn)和右端點(diǎn)分別設(shè)為第一，二關(guān)鍵字。然后限制左端點(diǎn)j（不斷往右移），然后對(duì)于當(dāng)前左端點(diǎn)是j的直接更新答案。答案要怎么求？有一個(gè)很機(jī)智的方法，就是把pk $p^k$ 拆成p,p2,p3......,pk $p,p^2,p^3......,p^k$ ，然后放進(jìn)一個(gè)數(shù)組里面，然后每次乘進(jìn)一個(gè)權(quán)值p。當(dāng)左端點(diǎn)右移的時(shí)候，就把對(duì)應(yīng)的p的逆元除掉，如果當(dāng)前p對(duì)應(yīng)的pk $p^k$ 在后面還有的話，那么再把p乘進(jìn)去（所以要維護(hù)一個(gè)next）。因?yàn)閜的加減至于k有關(guān)，所以可以維護(hù)最大值。然后動(dòng)態(tài)前綴積用樹狀數(shù)組就好了。其實(shí)還可以用莫隊(duì)強(qiáng)行輦過去。

Code

#include<iostream>#include<stdio.h>#include<string.h>#include<algorithm>#include<math.h>#define fo(i,a,b) for(i=a;i<=b;i++)using namespace std;typedef long long ll;const int maxn=5e4+7,mo=1e9+7;int i,j,k,n,m,ans[maxn],q,x,tot,a[maxn*10],b[maxn*10],c[maxn],l[maxn*10],r[maxn*10],next[maxn*10],d[maxn];ll t[maxn*10];bool bz[maxn];struct node{ int l,r,c;}wen[maxn];bool cmp(node x,node y){return x.l<y.l||x.l==y.l&&x.r<y.r;}ll qsm(ll x,ll y){ ll z=1; for(;y;y/=2,x=x*x%mo)if(y&1)z=z*x%mo; return z;}int lowbit(int x){return x&-x;}void add(int x,ll y){ for(;x<=tot;x+=lowbit(x))t[x]=t[x]*y%mo;}ll find(int x){ ll z=1; for(;x;x-=lowbit(x))z=z*t[x]%mo; return z;}int main(){ freopen("fan.in","r",stdin); scanf("%d%d",&n,&q); fo(i,1,n){ scanf("%d",&c[i]);x=c[i];l[i]=tot+1; fo(j,2,sqrt(c[i])){ k=1; while(x%j==0)k*=j,x/=j,a[++tot]=k,b[tot]=j; } if(x!=1)a[++tot]=b[tot]=x; r[i]=tot; } fo(i,1,tot)t[i]=1; fo(i,1,tot){ if(d[a[i]])next[d[a[i]]]=i; else add(i,b[i]); d[a[i]]=i; } fo(i,1,q)scanf("%d%d",&wen[i].l,&wen[i].r),wen[i].c=i,wen[i].l=l[wen[i].l],wen[i].r=r[wen[i].r]; sort(wen+1,wen+1+q,cmp);j=0; fo(i,1,tot){ while(wen[j+1].l==i)ans[wen[++j].c]=find(wen[j].r); add(i,qsm(b[i],mo-2)); if(next[i])add(next[i],b[i]); } fo(i,1,q)