1 条题解

  • 1
    @ 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%
上传者