Luogu

分析

先考虑乘积的约数个数怎么算。对其唯一分解成 $p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}$ 的形式,约数个数即为 $\prod_{i=1}^k(c_i+1)$。

一个想法是我们先对每个数质因数分解,这样子直接莫队求出一段区间的每个质因数的出现次数即可。

然而 $a_i\leq 10^9$,所以直接存肯定是存不下的。

考虑预处理出 $1000$ 以内的质数(只有 $168$ 个),这样子 $>1000$ 的质因子只有至多 $2$ 个。我们开一个大小为 $168$ 的桶记录 $\leq 1000$ 的质因数的出现次数,然后开一个大小为 $2n$ 的桶记录 $>1000$ 的质因数的出现次数即可。因为一些原因需要用 Pollard-Rho 来质因数分解。

可能有一些卡常,有一些比较有用的优化:预处理逆元(注意要预处理到 $2n$)、Pollard-Rho 时判掉完全平方数、预处理 $10^6$ 内的质数并在 MillerRabin 时直接判掉。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define ctz __builtin_ctz
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
using namespace std;
typedef long long ll;

namespace io {
    const int SIZE=1<<21;
    char ibuf[SIZE|1],*iS,*iT,obuf[SIZE|1],*oS=obuf,*oT=obuf+SIZE-1;
    void flush() { fwrite(obuf,1,oS-obuf,stdout); oS=obuf; }
    char getc() {
        if (iS==iT) {
            iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin);
            if (iS==iT) return EOF;
        }
        return *iS++;
    }
    void putc(char c) { *oS++=c; if (oS==oT) flush(); }
    int read() {
        int X=0; char c=getc();
        while (c<'0'||c>'9') c=getc();
        while (c>='0'&&c<='9') X=X*10+c-'0',c=getc();
        return X;
    }
    void write(int x) {
        if (!x) { putc('0'); return; }
        static int s[30]; int top=0;
        while (x) s[++top]=x%10,x/=10;
        while (top) putc(s[top--]+'0');
    }
    struct flusher { ~flusher() { flush(); } } io_flusher;
}
using io::putc;
using io::read;
using io::write;

const int N=100000+10,M=1000000+10;
const int mod=19260817;

int n,m,B,a[N],ans[N];
int inv[N<<1],sum[N][200];
struct query { int l,r,id; } q[N];
bool operator <(query a,query b) {
    if (a.l/B!=b.l/B) return a.l<b.l;
    else return (a.l/B)&1?a.r<b.r:a.r>b.r;
}

int p[M],id[M],v[M],pcnt=0;
void sieve(int n) {
    for (int i=2;i<=n;++i) {
        if (!v[i]) p[++pcnt]=i,id[i]=pcnt;
        for (int j=1;j<=pcnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]==0) break;
        }
    }
}

namespace PollardRho {
    vector<int> d;

    int qpow(int a,int b,int p) { int c=1;
        for (;b;b>>=1,a=1ll*a*a%p) if (b&1) c=1ll*c*a%p;
        return c;
    }
    int gcd(int a,int b) {
        if (!a||!b) return a|b;
        int t=ctz(a|b); a>>=ctz(a);
        do {
            b>>=ctz(b);
            if (a>b) swap(a,b);
            b-=a;
        } while (b);
        return a<<t;
    }

    const int p[2]={61,24251};
    bool isprime(int n) {
        if (n%6!=1&&n%6!=5) return 0;
        if (n<=1000000) return !v[n];
        int m=n-1,k=0;
        while (!(m&1)) m>>=1,++k;
        for (int ip=0;ip<2;++ip) {
            int x=qpow(p[ip],m,n),y=x;
            for (int i=1;i<=k;++i) {
                x=1ll*x*x%n;
                if (x==1&&y!=1&&y!=n-1) return 0;
                y=x;
            }
            if (x!=1) return 0;
        }
        return 1;
    }

    int f(int x,int c,int n) { return (1ll*x*x+c)%n; }
    int PollardRho(int n) {
        int s=0,t=0,c=rand()%(n-1)+1,w;
        for (int k=1;;s=t,k<<=1,w=1) {
            for (int i=1;i<=k;++i) {
                t=f(t,c,n); w=1ll*w*abs(t-s)%n;
                if (!(i&127)) {
                    int d=gcd(w,n);
                    if (d!=1) return d;
                }
            }
            int d=gcd(w,n);
            if (d!=1) return d;
        }
    }

    void calc(int n) {
        d.clear();
        if (isprime(n)) d.emplace_back(n);
        else {
            int r=(int)(sqrt(n)+0.5);
            if (r*r==n) {
                d.emplace_back(r),d.emplace_back(r);
            } else {
                int x=n;
                while (x==n) x=PollardRho(n);
                d.emplace_back(x),d.emplace_back(n/x);
            }
        }
    }
}

vector<int> d[N],S;

int cnt[N<<1],nans=1;
void add(int x) {
    for (int i:d[x]) {
        nans=1ll*nans*inv[cnt[i]]%mod;
        ++cnt[i];
        nans=1ll*nans*cnt[i]%mod;
    }
}
void del(int x) {
    for (int i:d[x]) {
        nans=1ll*nans*inv[cnt[i]]%mod;
        --cnt[i];
        nans=1ll*nans*cnt[i]%mod;
    }
}

int main() {
    srand(19491001);
    n=read(),m=read(); B=sqrt(n);
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=m;++i) q[i]=(query){read(),read(),i};
    sieve(1000000); inv[1]=1;
    for (int i=2;i<=n<<1;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    for (int i=1;i<=n;++i) {
        for (int j=1;j<=168;++j) sum[i][j]=sum[i-1][j];
        for (int j=1;j<=168&&p[j]*p[j]<=a[i];++j)
            while (a[i]%p[j]==0) ++sum[i][j],a[i]/=p[j];
        if (a[i]>1) {
            if (a[i]<=1000) ++sum[i][id[a[i]]];
            else {
                PollardRho::calc(a[i]);
                for (int j:PollardRho::d)
                    d[i].emplace_back(j),S.emplace_back(j);
            }
        }
    }
    sort(S.begin(),S.end()),S.erase(unique(S.begin(),S.end()),S.end());
    for (int i=1;i<=n;++i)
        for (int j=0;j<d[i].size();++j)
            d[i][j]=lower_bound(S.begin(),S.end(),d[i][j])-S.begin();
    sort(q+1,q+m+1);
    for (int i=0;i<S.size();++i) cnt[i]=1;
    for (int i=1,l=1,r=0;i<=m;++i) {
        while (l>q[i].l) --l,add(l);
        while (r<q[i].r) ++r,add(r);
        while (l<q[i].l) del(l),++l;
        while (r>q[i].r) del(r),--r;
        ans[q[i].id]=nans;
        for (int j=1;j<=168;++j)
            ans[q[i].id]=1ll*ans[q[i].id]*(sum[r][j]-sum[l-1][j]+1)%mod;
    }
    for (int i=1;i<=m;++i) write(ans[i]),putc('\n');
    return 0;
}
最后修改:2020 年 07 月 12 日 10 : 09 PM