珂朵莉的约数_牛客博客

题目描述

珂朵莉给你一个长为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

输出
复制

备注:
对于100%的数据，有n , m <= 100000 , a[i] <= 1000000

题解：

莫队+数论（约数个数）
很容易看出是莫队的题，个人认为难点在于求约数的个数，常规的求约束的个数肯定不行，有一个叫约束个数定理的东西
任何一个大于1的n都可以分解：
n=p1^a1×p2^a2×p3^a3*…*pk^ak,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]; // sum存 在区间内 > 1000 的素数的个数
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;
}