這就超級玄學啦><。
直接附上連結。
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)); } }
