CodeForces 385C Bear and Prime Numbers 素数打表-蒲公英云

CodeForces 385C Bear and Prime Numbers 素数打表

第一眼看这道题目的时候觉得可能会很难也看不太懂，但是看了给出的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;
}