题目链接:http://www.ifrog.cc/acm/problem/1153
题意:给你一个序列,每次查询一个区间
的乘积的约数个数
思路:官方题解:对每个数进行质因子分解,考虑一个数的约数个数即为其每个质因子出现次数的乘积,所以维护这个即可。考虑每个数只有一个大于
的质数,对这部分用根号分治。对于小于
的质因子(只有
个),维护一个前缀和
表示第
个质因子在前
个数中出现次数,对于大于
的质因子,用莫队维护即可。
反思:比赛的时候只想到了预处理前缀和后就没继续想了。。觉得肯定要。。。观察力还不够啊,每个数只有一个大于
的质数这个性质可以直接用莫队来维护觉得挺神奇的,收获挺大。
#pragma comment(linker, "/STACK:102400000,102400000") #include <map> #include <set> #include <stack> #include <queue> #include <cmath> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <cstring> #include <sstream> #include <cstdlib> #include <iostream> #include <algorithm> #define lson root<<1,l,mid #define rson root<<1|1,mid+1,r #define Key_Value ch[ch[root][1]][0] #define DBN1(a) cerr<<#a<<"="<<(a)<<"\n" #define DBN2(a,b) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n" #define DBN3(a,b,c) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n" #define DBN4(a,b,c,d) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n" #define DBN5(a,b,c,d,e) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n" #define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n" #define clr(a,x) memset(a,x,sizeof(a)) using namespace std; typedef long long ll; const int maxn=100000+5; const int maxm=1000+5; const int INF=0x3f3f3f3f; const int P=19260817; const double PI=acos(-1.0); template<typename T> inline T read(T&x){ x=0;int _f=0;char ch=getchar(); while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x=_f?-x:x; } int n,m,res=1,block[maxn],a[maxn],inv[maxn],ans[maxn],prime[maxm],num[maxm*maxm],pre[170][maxn]; bool isPrime[maxm]; struct Query{ int l,r,id; bool operator<(const Query&a)const{ if (block[l]==block[a.l]) return r<a.r; return block[l]<block[a.l]; } }q[maxn]; void inc(int x){ if(num[x]!=1) res=res*1LL*inv[num[x]]%P; res=res*1LL*(++num[x])%P; } void ins(int x){ if (a[x]!=1) inc(a[x]); } void dec(int x){ res=res*1LL*inv[num[x]--]%P; if (num[x]!=1) res=res*1LL*num[x]%P; } void des(int x){ if (a[x]!=1) dec(a[x]); } int ksm(int a,int n){ int res=1; while (n){ if (n&1) res=(1LL*res*a)%P; a=(1LL*a*a)%P; n>>=1; } return res; } void init(){ for (int i=2;i<=1000;i++){ if (!isPrime[i]) prime[++prime[0]]=i; for (int j=1;i*prime[j]<=1000 && j<=prime[0];j++){ isPrime[i*prime[j]]=true; if (i%prime[j]==0) break; } } for (int i=1;i<=n;i++){ for (int j=1;j<=prime[0];j++){ while (a[i]%prime[j]==0){ a[i]/=prime[j]; pre[j][i]++; } } } for (int i=1;i<=1000000;i++) num[i]=1; for (int j=1;j<=prime[0];j++){ for (int i=1;i<=n;i++){ pre[j][i]+=pre[j][i-1]; } } for (int i=1;i<=n+1;i++) inv[i]=ksm(i,P-2); } int main(){ read(n),read(m); for (int i=1;i<=n;i++) read(a[i]); init(); // int limit=n/sqrt(m/3); int limit=(int)sqrt(n+0.5); for (int i=1;i<=n;i++) block[i]=(i-1)/limit; for (int i=1;i<=m;i++){ read(q[i].l),read(q[i].r),q[i].id=i,ans[i]=1; int tmp; for (int j=1;j<=prime[0];j++)if (tmp=pre[j][q[i].r]-pre[j][q[i].l-1]) ans[i]=ans[i]*1LL*(tmp+1)%P; } sort(q+1,q+1+m); for (int i=1,l=1,r=0;i<=m;i++){ while (l>q[i].l) ins(--l); while (r<q[i].r) ins(++r); while (l<q[i].l) des(l++); while (r>q[i].r) des(r--); ans[q[i].id]=ans[q[i].id]*1LL*res%P; } for (int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }