Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast,no-stack-protector")
- #pragma GCC target("avx")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace __gnu_pbds;
- using namespace std;
- #define re return
- #define pb push_back
- #define all(x) (x).begin(), (x).end()
- #define fi first
- #define se second
- #define sqrt(x) sqrt(abs(x))
- #define mp make_pair
- #define pi (3.14159265358979323846264338327950288419716939937510)
- #define fo(i, n) for(int i = 0; i < n; ++i)
- #define ro(i, n) for(int i = n - 1; i >= 0; --i)
- #define unique(v) v.resize(unique(all(v)) - v.begin())
- template <class T> T abs (T x) { re x > 0 ? x : -x; }
- template <class T> T sqr (T x) { re x * x; }
- template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
- template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef pair<int, int> ii;
- typedef vector<ii> vii;
- typedef vector<string> vs;
- typedef double D;
- typedef long double ld;
- typedef long long ll;
- typedef pair<ll, ll> pll;
- typedef vector<ll> vll;
- typedef unsigned long long ull;
- typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> _tree;
- const int maxn = 1010;
- ull dp[maxn];
- vi v;
- int main() {
- for (int i = 2; i < 50; ++i) {
- bool check = true;
- for (int j = 2; j <= sqrt(i + 0.1); ++j) {
- if (i % j == 0) {
- check = false;
- break;
- }
- }
- if (check) v.pb(i);
- }
- fo(i, maxn) dp[i] = (ll) 1e18;
- dp[1] = 1;
- ull cur;
- int st;
- for (auto j : v) {
- //cout << "!!!!! " << j << endl;
- for (int i = maxn - 1; i > 0; --i) {
- st = 2, cur = j;
- while (st * i < maxn && cur * dp[i] <= (ll) 1e18) {
- if (dp[st * i] > cur * dp[i]) dp[st * i] = cur * dp[i];
- ++st;
- cur *= j;
- }
- //fo(i, 10) cout << dp[i] << ' ';
- //cout << endl;
- }
- }
- int n;
- cin >> n;
- cout << dp[n] << endl;
- re 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement