来源：牛客网：
题目描述
珂朵莉给你一个长为n的序列，有m次查询
每次查询给两个数l,r
设s为区间[l,r]内所有数的乘积
求s的约数个数mod 1000000007
输入描述: 第一行两个正整数n,m 第二行一个长为n的序列 之后m行每行两个数l和r 输出描述: 对于每个询问，输出一个整数表示答案 示例1 输入 复制
5 5
64 2 18 9 100
1 5
2 4
2 3
1 4
3 4
输出 复制
165
15
9
45
10
备注: 对于100%的数据，有n , m <= 100000 , a[i] <= 1000000
题解：
莫队+数论（约数个数） 很容易看出是莫队的题，个人认为难点在于求约数的个数，常规的求约束的个数肯定不行，有一个叫约束个数定理的东西 任何一个大于1的n都可以分解： n=p1a1×p2a2×p3a3*…*pkak,p为素数 而n的约数的个数就是(a1+1)(a2+1)(a3+1)…(ak+1) 再看一下本题数据，对于不超过1000的素数我们可以直接维护每个素数的幂指数+1的前缀乘积（共168个），而超过1000的素因数最多也就一个。代码中ant用来记录1000之外的素因子，res用来记录1000之内的每个素数的幂指数+ 1 +1+1的前缀乘积 线性筛就是每一次被最小素因数给筛出来，所以用线性筛来计算因数和。因为题目要mod，所以我们还要线性预处理逆元，方便后面使用
nv
[0] = inv
[1] = 1; for(int i
=2;i
<=n
+1;i
++) inv
[i
]=1ll*(MOD
-MOD
/i
)*inv
[MOD
%i
]%MOD
;
具体线性筛如何求因数和可以看其他博客讲解 具体代码如下
代码：
#include <bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const int N
= 1e5 + 10;
const int MOD
= 1e9+7;
int prime
[1007],tot
;
bool vis
[1007];
ll inv
[N
],ans
[N
],ant
;
int Be
[N
],a
[N
],sum
[N
*10],pre
[N
][170];
void init()
{
tot
= 0;
for(int i
= 2;i
<= 1000;i
++)
{
if(vis
[i
]) continue;
prime
[tot
++] = i
;
for(int j
= i
+ i
; j
<= 1000; j
+= i
)
vis
[j
] = 1;
}
}
struct Mo
{
int l
,r
,id
;
}Q
[N
];
int cmp(Mo a
,Mo b
){ return Be
[a
.l
] == Be
[b
.l
] ? a
.r
< b
.r
: a
.l
< b
.l
;}
void add(int pos
)
{
if(a
[pos
] == 1) return;
ant
= ant
*inv
[1+sum
[a
[pos
]]]%MOD
;
sum
[a
[pos
]]++;
ant
= ant
*(1+sum
[a
[pos
]])%MOD
;
}
void del(int pos
)
{
if(a
[pos
] == 1) return;
ant
= ant
*inv
[1+sum
[a
[pos
]]]%MOD
;
sum
[a
[pos
]]--;
ant
= ant
*(1+sum
[a
[pos
]])%MOD
;
}
int main()
{
int n
,m
;
init();
scanf("%d%d",&n
,&m
);
inv
[0] = inv
[1] = 1; for(int i
=2;i
<=n
+1;i
++) inv
[i
]=1ll*(MOD
-MOD
/i
)*inv
[MOD
%i
]%MOD
;
int len
= sqrt(n
);
for(int i
= 1;i
<= n
;i
++)
{
scanf("%d",&a
[i
]);
Be
[i
] = i
/len
;
for(int j
= 0;j
< tot
;j
++)
{
pre
[i
][j
] = pre
[i
-1][j
];
while(a
[i
] % prime
[j
] == 0)
{
pre
[i
][j
]++;
a
[i
] /= prime
[j
];
}
}
}
for(int i
= 1;i
<= m
;i
++) scanf("%d%d",&Q
[i
].l
,&Q
[i
].r
),Q
[i
].id
= i
;
sort(Q
+1,Q
+m
+1,cmp
);
memset(sum
,0,sizeof(sum
));
ant
= 1;
int l
= 1,r
= 0;
for(int i
= 1;i
<= m
;i
++)
{
while(r
< Q
[i
].r
) add(r
+1),r
++;
while(r
> Q
[i
].r
) del(r
),r
--;
while(l
< Q
[i
].l
) del(l
),l
++;
while(l
> Q
[i
].l
) add(l
-1),l
--;
ll res
= 1;
for(int j
=0;j
<tot
;j
++)
res
=1ll*res
*(pre
[r
][j
]-pre
[l
-1][j
]+1)%MOD
;
ans
[Q
[i
].id
] = 1ll*ant
*res
%MOD
;
}
for(int i
= 1;i
<= m
;i
++)
printf("%lld\n",ans
[i
]);
return 0;
}
