鏈接：https://www.nowcoder.com/acm/contest/40/F
來源：牛客網

珂朵莉給你一個長為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 - 1e6 范圍的數他大于1e3的素數因子最多只有一個，我們可以用莫隊來維護他，但對于1 - 1e3的來說最多有168個素數因子，所以用一個前綴和，來解決

調了一天的莫隊，wawawawa 很迷茫，然后將那4個while 順序轉換一下，然后就A了。。。。。。。。（真是搞不清楚為啥會 Wa）

AC code: #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; }

?

轉載于:https://www.cnblogs.com/lemon-jade/p/9453034.html

總結

以上是生活随笔為你收集整理的珂朵莉的约数（牛客练习赛9）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。