P r o Pro P r o
珂朵莉给你了一个长为n n n 的序列,有m m m 次查询,每次查询一段区间的乘积的约数个数m o d 19260817 \mod 19260817 m o d 1 9 2 6 0 8 1 7 的值
n , m ≤ 100000 n,m\le 100000 n , m ≤ 1 0 0 0 0 0
1 ≤ a i ≤ 1000000000 1 \le a_i \le 1000000000 1 ≤ a i ≤ 1 0 0 0 0 0 0 0 0 0
S o l Sol S o l
首先,根据小学奥数(雾),设D ( x ) D(x) D ( x ) 为x x x 的约数个数,设x = ∏ p i k i ( p i ∈ prime ) x=\prod p_i^{k_i} (p_i \in \text{prime}) x = ∏ p i k i ( p i ∈ prime ) ,我们有
D ( x ) = ∏ ( k i + 1 ) D(x)=\prod (k_i+1) D ( x ) = ∏ ( k i + 1 ) 。
于是,每次莫队转移的时候,我们把新加进的那个数(设为A A A )分解质因数,假设现在分解出了一个质数p p p ,那么答案× i n v ( c n t [ p ] + 1 ) \times inv(cnt[p]+1) × i n v ( c n t [ p ] + 1 ) ,然后c n t [ p ] + + cnt[p]++ c n t [ p ] + + ,最后× ( c n t [ p ] + 1 ) \times (cnt[p]+1) × ( c n t [ p ] + 1 ) ,但是这样肯定会炸掉,因为质因数很多,考虑到A A A 的质因数很多都是< 1000 <1000 < 1 0 0 0 ,根据其他题解中的说法:A A A 最多也只有两个> 1000 >1000 > 1 0 0 0 的质因数。
所以,方法就有了,考虑把< 1000 <1000 < 1 0 0 0 的和≥ 1000 \geq 1000 ≥ 1 0 0 0 的质数分开考虑,因为< 1000 <1000 < 1 0 0 0 的质数只有169 169 1 6 9 个,所以每次重新算也没有关系,≥ 1000 \geq 1000 ≥ 1 0 0 0 的质数就按照上面方法维护就可以了。
再看怎么具体实现,首先预处理逆元和线性筛质数都是必须的
1. 1. 1 . 考虑维护< 1000 <1000 < 1 0 0 0 的质数对答案的贡献,维护一个前缀和数组s u m sum s u m ,其中s u m [ i ] [ p ] sum[i][p] s u m [ i ] [ p ] 代表∏ j = 1 i a j \prod_{j=1}^{i} a_j ∏ j = 1 i a j 中p p p 出现的次数,求∏ j = l r a j \prod_{j=l}^{r} a_j ∏ j = l r a j 中p p p 出现的次数,就是前缀和做一下差,即s u m [ r ] [ p ] − s u m [ l − 1 ] [ p ] sum[r][p]-sum[l-1][p] s u m [ r ] [ p ] − s u m [ l − 1 ] [ p ] 。
2. 2. 2 . 考虑维护≥ 1000 \geq 1000 ≥ 1 0 0 0 的质数对答案的贡献,由于≥ 1000 \geq1000 ≥ 1 0 0 0 的质数比较多,不好记录,又发现其实答案只和k i k_i k i 有关,和p i p_i p i 是没关的,所以只要统计不同的数的个数即可,我们这里用一种比较偷懒的办法,新来一个数,我们把它扔进一个m a p map m a p 里面,如果他出现过,那么记录他在m a p map m a p 里面的编号,否则新建一个编号,这样就起到去重和离散化 的效果(这种办法太偷懒了,导致程序效率不高),最后像上面说的一样,莫队维护一下。
注意:中间量要开long long \text{long long} long long ,使劲卡常,此代码多交几次或许能A C \rm AC A C
时间复杂度O ( n n ∗ 169 ) O(n \sqrt{n}*169) O ( n n ∗ 1 6 9 )
总结一下,质数在一段区间的稠密度是不同的,标程就是根据这个性质,分布稠密的小范围暴力搞,分布稀疏的大范围莫队搞,这是一种重要的思想。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 #include <bits/stdc++.h> #pragma GCC optimize(3) #define MOD 19260817 #define MAXN 200005 #define MAXP 32005 #define CNT 169 #define ll long long using namespace std;inline int read () { int x=0 ,f=1 ; char ch=getchar (); while (ch<'0' ||ch>'9' ){ if (ch=='-' ) f=-1 ; ch=getchar (); } while (ch>='0' &&ch<='9' ){ x=(x<<1 )+(x<<3 )+(ch^'0' ); ch=getchar (); } return x*f; } static int inv[MAXN];static int nprime[MAXN];static int cnt,prime[MAXN],pos[MAXN];inline int ksm (int b,int k) { int ans=1 ; while (k){ if (k&1 ) ans=((long long )ans*(long long )b)%MOD; b=((long long )b*(long long )b)%MOD; k>>=1 ; } return ans; } inline void Init (int n) { for (register int i=0 ;i<MAXN;++i){ inv[i]=ksm (i,MOD-2 )%MOD; } for (register int i=2 ;i<MAXP;++i){ if (!nprime[i]){ for (register int j=i*2 ;j<MAXP;j+=i){ nprime[j]=true ; } } } for (register int i=2 ;i<MAXP;++i){ if (!nprime[i]) prime[++cnt]=i; } int Size=sqrt (n); for (register int i=1 ;i<=n;++i){ pos[i]=(i-1 )/Size+1 ; } } static int sum[MAXN][CNT];static int v[MAXN][CNT],top[MAXN];static map<int ,int >M;inline void AddV (int i,int val) { if (M.count (val)==0 ) v[i][++top[i]]=M[val]=M.size ()+1 ; else v[i][++top[i]]=M[val]; } struct Query { int l,r,id; }q[MAXN]; inline bool operator < (const Query &A,const Query &B){ return pos[A.l]<pos[B.l]||(pos[A.l]==pos[B.l]&&((pos[A.l]&1 )?A.r<B.r:A.r>B.r)); } int ans;static int c[MAXN];inline void Add (int x) { for (register int i=1 ;i<=top[x];++i){ ans=((long long )ans*inv[c[v[x][i]]+1 ])%MOD; ++c[v[x][i]],c[v[x][i]]%=MOD; ans=((long long )ans*(c[v[x][i]]+1 ))%MOD; } } inline void Del (int x) { for (register int i=1 ;i<=top[x];++i){ ans=((long long )ans*(inv[c[v[x][i]]+1 ]))%MOD; --c[v[x][i]],(c[v[x][i]]+=MOD)%=MOD; ans=((long long )ans*(c[v[x][i]]+1 ))%MOD; } } static int Ans[MAXN];int main () { int n=read (),m=read (); Init (n); for (register int i=1 ;i<=n;++i){ int a=read (); for (register int j=1 ;j<CNT;++j){ sum[i][j]=sum[i-1 ][j]; while (a%prime[j]==0 ){ a/=prime[j],++sum[i][j]; } } if (a==1 ) continue ; for (register int j=CNT;j<=cnt;++j){ if (a==1 ) break ; while (a%prime[j]==0 ){ a/=prime[j],AddV (i,prime[j]); } } if (a!=1 ) AddV (i,a); } for (register int i=1 ;i<=m;++i){ int l=read (),r=read (); q[i].l=l,q[i].r=r,q[i].id=i; } sort (q+1 ,q+1 +m); register int l=1 ,r=0 ; ans=1ll ; for (register int i=1 ;i<=m;++i){ while (l>q[i].l) Add (--l); while (r<q[i].r) Add (++r); while (l<q[i].l) Del (l++); while (r>q[i].r) Del (r--); Ans[q[i].id]=ans; for (register int j=1 ;j<CNT;++j){ Ans[q[i].id]=((long long )Ans[q[i].id]*(sum[r][j]-sum[l-1 ][j]+1 ))%MOD; } } for (register int i=1 ;i<=m;++i){ printf ("%d\n" ,Ans[i]); } }