公司网站开发策划,口碑好的微信网站建设,计算机网站建设目标,wordpress采集视频教程来源#xff1a;牛客网#xff1a;
题目描述
珂朵莉给你一个长为n的序列#xff0c;有m次查询
每次查询给两个数l,r
设s为区间[l,r]内所有数的乘积
求s的约数个数mod 1000000007
输入描述: 第一行两个正整数n,m 第二行一个长为n的序列 之后m行每行两个数l和r 输出描述…来源牛客网
题目描述
珂朵莉给你一个长为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都可以分解 np1a1×p2a2×p3a3*…*pkak,p为素数 而n的约数的个数就是(a11)(a21)(a31)…(ak1) 再看一下本题数据对于不超过1000的素数我们可以直接维护每个素数的幂指数1的前缀乘积共168个而超过1000的素因数最多也就一个。代码中ant用来记录1000之外的素因子res用来记录1000之内的每个素数的幂指数 1 11的前缀乘积 线性筛就是每一次被最小素因数给筛出来所以用线性筛来计算因数和。因为题目要mod所以我们还要线性预处理逆元方便后面使用
nv[0] inv[1] 1; for(int i2;in1;i) inv[i]1ll*(MOD-MOD/i)*inv[MOD%i]%MOD ; 具体线性筛如何求因数和可以看其他博客讲解 具体代码如下
代码
#include bits/stdc.husing namespace std;
typedef long long ll;
const int N 1e5 10;
const int MOD 1e97;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[1sum[a[pos]]]%MOD;sum[a[pos]];ant ant*(1sum[a[pos]])%MOD;
}
void del(int pos)
{if(a[pos] 1) return;ant ant*inv[1sum[a[pos]]]%MOD;sum[a[pos]]--;ant ant*(1sum[a[pos]])%MOD;
}
int main()
{int n,m;init();scanf(%d%d,n,m);inv[0] inv[1] 1; for(int i2;in1;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(Q1,Qm1,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(r1),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 j0;jtot;j)res1ll*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;
}
