#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include using namespace std; using u32 = uint32_t; using u64 = uint64_t; vector sieve_of_atkin(int N){ vector isprime(N + 1); const int sqrtN = sqrt(N); int n; for(int z = 1; z <= 5; z += 4) for(int y = z; y <= sqrtN; y += 6){ for(int x = 1; x <= sqrtN && (n = 4*x*x+y*y) <= N; ++x) isprime[n] = !isprime[n]; for(int x = y+1; x <= sqrtN && (n = 3*x*x-y*y) <= N; x += 2) isprime[n] = !isprime[n]; } for(int z = 2; z <= 4; z += 2) for(int y = z; y <= sqrtN; y += 6){ for(int x = 1; x <= sqrtN && (n = 3*x*x+y*y) <= N; x += 2) isprime[n] = !isprime[n]; for(int x = y+1; x <= sqrtN && (n = 3*x*x-y*y) <= N; x += 2) isprime[n] = !isprime[n]; } for(int y = 3; y <= sqrtN; y += 6) for(int z = 1; z <= 2; ++z){ for(int x = z; x <= sqrtN && (n = 4*x*x+y*y) <= N; x += 3) isprime[n] = !isprime[n]; } for(int n = 5; n <= sqrtN; ++n) if(isprime[n]) for(int k = n*n; k <= N; k+=n*n) isprime[k] = false; isprime[2] = isprime[3] = true; return isprime; } vector primes(int N){ auto isprime = sieve_of_atkin(N); vector ans; for(int i = 2; i <= N; i++) if(isprime[i]) ans.push_back(i); return ans; } int main(){ constexpr u32 MAX = 5987010; // 整数に丸めた時の誤差が小さくなるマジックナンバー u32 N; u64 K; cin >> N >> K; if(K == 1) return puts("1") & 0; const vector P = primes(N); // log を取ってナップサック DP const u32 lgK = round(logl(K) / logl(1e10) * MAX); vector lg(N + 1); // log の概算値 log(1e10) = MAX になるように定数倍して、整数に丸める for(u32 i : P) lg[i] = round(logl(i) / logl(1e10) * MAX); for(u32 p : P) for(u32 i = 2; i * p <= N; i++) lg[i * p] = lg[i] + lg[p]; // ナップサック DP vector dp(MAX + 1); dp[0] = 2; for(u32 i = 2; i <= N; i++){ const u32 x = lg[i]; for(u32 i = MAX; i >= x; i--) dp[i] += dp[i - x]; } // このままだと、K 以下が入っていなかったり K より大きいのが入っていたりする // K より大きいのが入らないように狭める dp.resize(lgK - 2); u64 ans = accumulate(dp.begin(), dp.end(), -1LL); // K 以下で入っていないものを追加する auto solve = [N](u64 x) -> u32 { // 積が x になる個数を x の約数上の DP で求める unordered_map, map は遅いのでソート済み列の merge を使う vector> dp = {{1, 2}}; for(u32 j = 2; j <= N; j++) if(x % j == 0){ auto update = [x, j](pair& a){ a.first *= j; if(a.first < x && x % a.first) a.first = 0; }; vector> dp2; u32 p = 0, q = 0; while(q < dp.size()){ if(dp[q].first == 0){ q++; continue; } if(p < dp.size()){ if(p == q || dp[p].first < dp[q].first){ dp2.push_back(dp[p]); update(dp[p]); p++; } else if(dp[p].first == dp[q].first){ dp2.emplace_back(dp[p].first, dp[p].second + dp[q].second); update(dp[p]); p++; q++; } else{ dp2.push_back(dp[q]); q++; } continue; } if(dp[q].first > x) break; dp2.push_back(dp[q]); q++; } swap(dp, dp2); } if(dp.back().first != x) return 0; return dp.back().second; }; // K 以下で入っていないものを追加する for(u64 i = max(2, K - 1e6); i <= K; i++){ u64 x = i; u32 y = 0; // 素因数分解してチェック for(u32 p : P) while(x % p == 0){ x /= p; y += lg[p]; } if(y >= dp.size()) ans += solve(i); } cout << ans << endl; }