CodeForces 385C Bear and Prime Numbers 素数打表

ゞ浴缸里的玫瑰 2021-12-10 16:45 182阅读 0赞

第一眼看这道题目的时候觉得可能会很难也看不太懂，但是看了给出的Hint之后思路就十分清晰了

Consider the first sample. Overall, the first sample has 3 queries.
    
    The first query l = 2, r = 11 comes. You need to count f(2) + f(3) + f(5) + f(7) + f(11) = 2 + 1 + 4 + 2 + 0 = 9.
    The second query comes l = 3, r = 12. You need to count f(3) + f(5) + f(7) + f(11) = 1 + 4 + 2 + 0 = 7.
    The third query comes l = 4, r = 4. As this interval has no prime numbers, then the sum equals 0.

xn的范围在(2 ≤ *x**i* ≤ 107)，而 l, r 的范围在 (2 ≤ *l**i* ≤ *r**i* ≤ 2·109) ，易得在计算的时候是不会考虑107  以后了

首先写一个素数快速打表，同时也统计一下在 l, r 范围内每个数满足题目条件的总数 (虽然觉得这样的打表方法的确很慢)

然后注意了，因为查询的次数很多，多达5\*104次 ，所以在统计的时候可以算出累计和以节省时间

Source Code:

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
    #include <stdio.h>
    #include <iostream>
    #include <fstream>
    #include <cstring>
    #include <cmath>
    #include <stack>
    #include <string>
    #include <map>
    #include <set>
    #include <list>
    #include <queue>
    #include <vector>
    #include <algorithm>
    #define Max(a,b) (((a) > (b)) ? (a) : (b))
    #define Min(a,b) (((a) < (b)) ? (a) : (b))
    #define Abs(x) (((x) > 0) ? (x) : (-(x)))
    #define MOD 1000000007
    #define pi acos(-1.0)
    
    using namespace std;
    
    typedef long long           ll      ;
    typedef unsigned long long  ull     ;
    typedef unsigned int        uint    ;
    typedef unsigned char       uchar   ;
    
    template<class T> inline void checkmin(T &a,T b){
        if(a>b) a=b;}
    template<class T> inline void checkmax(T &a,T b){
        if(a<b) a=b;}
    
    const double eps = 1e-7      ;
    const int N = 210            ;
    const int M = 1100011*2      ;
    const ll P = 10000000097ll   ;
    const int MAXN = 10900000    ;
    
    int cnt[MAXN],a[MAXN];
    bool check[MAXN];
    
    void init_prime(){
        for(int i = 2; i < MAXN; ++i){ //素数打表
            if(!check[i]){
                for(int j = i; j < MAXN; j += i){
                    check[j] = true;
                    cnt[i] += a[j];
                }
            }
        }
    }
    
    int main(){
        std::ios::sync_with_stdio(false);
        int i, j, t, k, u, v, numCase = 0;
        int n, q, x, y;
        cin >> n;
        for(i = 1; i <= n; ++i){
                cin >> x;
                ++a[x];
        }
        init_prime();
        for(i = 2; i < MAXN; ++i){
            cnt[i] += cnt[i - 1];   //作累计和以节省查询时间
        }
        cin >> t;
        while(t--){
                cin >> x >> y;
                checkmin(x, 10000000);
                checkmin(y, 10000000);
                cout << cnt[y] - cnt[x - 1] << endl;
        }
        return 0;
    }

转载于:https://www.cnblogs.com/wushuaiyi/p/4314071.html