1 条题解
-
1XzyStudio (admin) LV 8 MOD RP++ 机房蒟蒻 tayz @ 2023-10-11 17:11:40
质数统计(prime)
用一个桶记录每种输入数字的出现次数,然后利用Eratosthenes筛法(埃氏筛)枚举每个质数的倍数统计每个质数对答案的贡献,将贡献数组求前缀和后就可以\(0(1)\)回答每次询问了
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<ctime> #include<algorithm> #define MAXN 10000005 #define MOD 1000000007 using namespace std; inline int read() { int num=0,sgn=1; char ch=getchar(); while (ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if (ch=='-')sgn=-1,ch=getchar(); while (ch>='0'&&ch<='9')num*=10,num+=ch-'0',ch=getchar(); return num*sgn; } int n,m,l,r,x; int num[MAXN],cnt[MAXN]; bool vis[MAXN]; int main() { n=read();m=read(); for (int i=1;i<=n;i++) { x=read(); num[x]++; } for (int i=2;i<MAXN;i++) if (!vis[i])for (int j=i;j<MAXN;j+=i) { vis[j]=1; cnt[i]+=num[j]; cnt[i]%=MOD; } for (int i=2;i<MAXN;i++) { cnt[i]+=cnt[i-1]; cnt[i]%=MOD; } while (m--) { l=read();r=read(); printf("%d\n",(cnt[r]-cnt[l-1]+MOD)%MOD); } return 0; }
- 1
信息
- ID
- 1014
- 难度
- 8
- 分类
- (无)
- 标签
- 递交数
- 41
- 已通过
- 6
- 通过率
- 15%
- 上传者