【51 Nod 1203】JZPLCM

2019-11-11 01:12:01

字體：大中小

來源：轉載

供稿：網友

Description

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

Solution

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

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)