#include #include #include #include #include #include #include #include #include #include #include #include #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; using P = pair; class Eratosthenes{ public: int m; vector is_prime; vector primes; Eratosthenes(int m_){ m = m_; init(); } private: void init(){ is_prime.assign(m+1, true); is_prime[0] = false, is_prime[1] = false; for(int i = 2; i <= m; i++){ if(is_prime[i]){ primes.push_back(i); for(int j = 2; i*j <= m; j++) is_prime[i*j] = false; } } } }; vector

factorize(int n){ int m = n; vector

ans; for(int i = 2; i*i <= n; i++){ if(m%i == 0){ int cnt = 0; while(m%i == 0){ cnt++; m /= i; } ans.push_back(P(i, cnt)); } } if(m != 1) ans.push_back(P(m, 1)); return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; int n; cin >> n; Eratosthenes erat(n); int m = erat.primes.size(); vector p; for(int x : erat.primes){ if(x*x > n) break; p.push_back(x); } int k = p.size(); vector> facs(1< n) { s = -1; break; } int idx = [&](int x){ for(int i = 0; i < k; i++){ if(p[i] == x) return i; } }(x); s |= (1< 0) facs[s].push_back(i); } facs[0].push_back(1); vector u; for(int i = 0; i < (1<> dp(m+1, vector(1<