(HDU) 5901. Count primes [pi函數，求一個數之前有多少質數]

http://acm.hdu.edu.cn/showproblem.php?pid=5901

這就超級玄學啦><。

直接附上連結。

code:

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cassert>
#include <iomanip>
#include <bitset>
using namespace std;

typedef long long      LL;
typedef long double    ld;
typedef pair<int,int>  pii;
typedef pair<LL,LL>    pLL;
typedef vector<int>    vint;
typedef vector<LL>     vLL;
typedef vector<pii>    vpii;
typedef vector<pLL>    vpLL;

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a)*1LL,(b)*1LL,(c)*1LL,(d)*1LL,(e)*1LL);
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a)*1LL,(b)*1LL,(c)*1LL,(d)*1LL,(e)*1LL,(f)*1LL);

#define Pi1(x) printf("%d",  (x));
#define PL1(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)

#define IOS ios::sync_with_stdio(0); cin.tie(0);

int myRnd() {
    return abs(  ((rand()<<15) ^ rand()) );
}

int myRnd(int L,int R) {
    return abs(( (rand()<<15)^rand() ) ) % (R-L+1) + L;
}

void Parr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++) {
        printf("%d%c",arr[i]," \n"[i==R]);
    }
}

void Pvec(vint v) {
    for (int i=0;SZ(v)>i;i++) {
        printf("%d%c",v[i]," \n"[i==SZ(v)-1]);
    }
}

void Sarr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++)
    {
        Si(arr[i]);
    }
}

const int N = 320000 + 6;
const int C = 15005;
const int D = 506;

LL pi_form[N];
LL phi_form[C][D];
//LL p2_form[C][D];
LL p[N];
bool prime[N];

void init()
{
    MEM1(phi_form);
//    MEM1(p2_form);
    prime[0] = prime[1] = 1;
    int id=1;
    for (int i=2;N>i;i++)
    {
        if (!prime[i])
        {
            for (LL j=i*1LL*i;N>j;j+=i)
            {
                prime[j] = 1;
            }
            p[id++] = i;
        }
        pi_form[i] = pi_form[i-1] + (!prime[i]);
    }
}

LL pi(LL m);

LL p2(LL m,LL n)
{
    //cout<<"p2 = "<<p2_form[m][n]<<endl;
    //if (m<C && n<D && p2_form[m][n] != -1) return p2_form[m][n];
    //if (p[n] == 0) return 0;
    LL ret = 0;
    LL tmp=sqrt(m);
    for (LL i=n+1;p[i] <= tmp;i++)
    {
        ret += pi(m/p[i]) - pi(p[i]) + 1;
    }
    //if (m < C && n < D) p2_form[m][n] = ret;
    return ret;
}

LL phi2(LL m,LL n)
{
    if (m < C && n < D && phi_form[m][n] != -1) return phi_form[m][n];
    if (!n) return m;
    if (p[n] >= m) return 1;
    if (m<C && n<D) return phi_form[m][n] =  phi2(m,n-1) - phi2(m/p[n],n-1);
    return phi2(m,n-1) - phi2(m/p[n],n-1);
}

LL pi(LL m)
{
    //cout<<"pi = "<<m<<endl;
    if (m < N) return pi_form[m];
    else
    {
        LL n=ceil(cbrt(m));
        return phi2(m,n) + n - 1 - p2(m,n);
    }
}

int main () {
    //srand(time(NULL));
    init();
    LL n;
    while (scanf("%lld",&n) != EOF)
    {
        PL(pi(n));
    }
}