#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; const int MAX=1000000; bitset isprime; void sieve(){ for(int i=3; i divs, pc; inline ll idx(ll x){ return (x<=sq)?x-1:(ll)divs.size()-n/x; } void calc(){ sieve(); while((sq+1)*(sq+1)<=n) sq++; for(int i=1; i<=sq; i++) divs.push_back(i); for(int i=sq; i>=1; i--) if(n/i>sq) divs.push_back(n/i); int k=0; isq=-1; for(int i=2; isq && isq==-1) isq=k; k++; } } } void primecount(){ vector dp=divs; pc.resize(divs.size(), -1); int l; for(l=0; l=l; j--){ int k=idx(divs[j]/p[i-1]); if(pc[k]!=-1){ dp[j]-=pc[k]-i+2; }else{ dp[j]-=dp[k]; } } for(int j=l; j dp(divs.size()); for(int i=isq-1; i>=0; i--){//isqをisq-1に変更 int l=lower_bound(divs.begin(), divs.end(), p[i]*(p[i]-1))-divs.begin(); for(int j=(int)divs.size()-1; j>=l; j--){ ll q=p[i]-1; ll a=dp[j]; if(p[i+1]*(p[i+1]-1)>divs[j]){ a=1+pc[j]-(i+1); } while(divs[j]>=q){ ll x=divs[j]/q; int k=idx(x); ll b=dp[k]; if(xx){ b=1+pc[k]-(i+1); } a+=b; q*=p[i]; } dp[j]=a; } } dp[0]=2; return dp.back(); } ll powmod(__int128_t a, ll k, ll m){ __int128_t ap=a, ans=1; while(k){ if(k&1){ ans*=ap; ans%=m; } k>>=1; ap=ap*ap%m; } return ans; } bool is_prime(ll n){ if(n>=1; k++; } vector va{2, 325, 9375, 28178, 450775, 9780504, 1795265022}; // http://miller-rabin.appspot.com/ for(auto aa:va){ ll a=aa%n; if(a==0) continue; bool comp=1; ll ap=powmod(a, d, n); if(ap==1 || ap==n-1) continue; for(int r=1; r>n; calc(); primecount(); for(int i=0; i