FINDNUM - Tìm số

Tác giả: happyboy99x

Ngôn ngữ: C++

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

typedef long long LL;
const LL INF = (LL) 1e18;//1000000000

LL prime[] = {0, 2,3,5,7,11,13,17,19,23,29};
LL mxpow[] = {0, 59,37,25,21,17,16,14,14,13,12};
int n;
LL dp[1005][11];
//dp[i][j] smallest number have i divisor, use only j-first prime number

int main() {
	scanf("%d",&n);
	fo(i,1,n) rep(j,11) {
		if(i == 1) dp[i][j] = 1;
		else if(j == 0) dp[i][j] = LLONG_MAX;
		else {
			dp[i][j] = dp[i][j-1];
			for(LL mul = prime[j], k = 1; k <= mxpow[j]; ++k, mul *= prime[j]) {
				if( i % (k+1) == 0 && dp[i/(k+1)][j-1] <= INF/mul )
					dp[i][j] = min(dp[i][j], dp[i/(k+1)][j-1] * mul);
			}
		}
	}
	cout << dp[n][10] << endl;
	return 0;
}

Download