#define rep(i,n) for(int i=0;i<(int)(n);i++) #define ALL(v) v.begin(),v.end() typedef long long ll; #include using namespace std; template using V=vector; template using VV=V>; struct Eratosthenes{ vector isprime; vector minfactor; vector mobius; vector mu; //メビウス関数もどき(互いに素でない組を数えるときに使う) Eratosthenes(int N) : isprime(N+1,true), minfactor(N+1,-1), mobius(N+1,1), mu(N+1,-1){ isprime[0]=false; isprime[1]=false; minfactor[1]=1; mu[1]=0; for(int p=2;p<=N;++p){ if(!isprime[p]) continue; minfactor[p]=p; mobius[p]=-1; for(int q=p*2;q<=N;q+=p){ isprime[q]=false; if(minfactor[q]==-1) minfactor[q]=p; if((q/p)%p==0) mobius[q]=0; else mobius[q]=-mobius[q]; } for(int i=p;i<=N;i+=p) mu[i]=-mu[i]; //mu for(ll i=(ll)p*p;i<=N;i+=(ll)p*p) mu[i]=0; //mu } } // 高速素因数分解 // pair (素因子, 指数) の vector を返す vector> factorize(int n){ vector> res; while(n>1){ int p=minfactor[n]; int exp=0; while(minfactor[n]==p){ n/=p; ++exp; } res.emplace_back(p, exp); } return res; } // 高速約数列挙 vector divisors(int n){ vector res({1}); auto pf=factorize(n); for(auto p:pf){ int s=(int)res.size(); for(int i=0;i>n; V A; rep(i,1000){ if(er.isprime[i]) A.push_back(i); } V B; ll tmp=1; rep(i,(int) A.size()){ if(tmp>n/A[i]) break; tmp*=A[i]; B.push_back(tmp); } auto ans=lower_bound(ALL(B),n)-B.begin(); cout<