codeforces 515C 题目解答:定义 f(n)=n 这个数各个位置上的数的阶乘的乘积。
给你 a; 让你另外求一个不含 0 和 1 的最大的数字 b; 使得 f(a)==f(b)
【题解】对 a 的每一个大于 1 的数字进行分解; 看看它能够组合成的最多的比它小的数字的阶乘的乘积是哪些; 比如
- #include using namespace std;#define lson l,
- m,
- rt << 1#define rson m + 1,
- r,
- rt << 1 | 1#define LL long long#define rep1(i, a, b) for (int i = a; i <= b; i++)#define rep2(i, a, b) for (int i = a; i >= b; i--)#define mp make_pair#define ps push_back#define fi first#define se second#define rei(x) scanf("%d", &x)#define rel(x) scanf("%lld", &x)#define ref(x) scanf("%lf", &x) typedef pair pii;
- typedef pair pll;
- const int dx[9] = {
- 0,
- 1,
- -1,
- 0,
- 0,
- -1,
- -1,
- 1,
- 1
- };
- const int dy[9] = {
- 0,
- 0,
- 0,
- -1,
- 1,
- -1,
- 1,
- -1,
- 1
- };
- const double pi = acos( - 1.0);
- const int N = 12;
- LL fac[N];
- vector fenjie[N];
- int a[N],
- ans[N];
- int n,
- temp[20],
- final_ans[200],
- num = 0;
- char s[20];
- void dfs(int x, int pos, int num, LL now) {
- if (x > 9) {
- if (now == fac[pos]) {
- if (num > ans[pos]) {
- ans[pos] = num;
- fenjie[pos].clear();
- rep1(i, 2, 9) {
- int len = a[i];
- rep1(j, 1, len) fenjie[pos].ps(i);
- }
- }
- }
- return;
- }
- LL temp = 1;
- int tot = 0;
- while (1LL * temp * fac[x] <= fac[pos]) {
- tot++;
- temp = 1LL * temp * fac[x];
- }
- rep2(i, tot, 0) {
- if (now * temp <= fac[pos]) {
- a[x] = i;
- dfs(x + 1, pos, num + i, now * temp);
- a[x] = 0;
- }
- temp /= fac[x];
- }
- }
- bool cmp(int a, int b) {
- return a > b;
- }
- int main() { //freopen("F:\\rush.txt", "r", stdin); fac[0] = fac[1] = 1; rep1(i, 2, 9) fac[i] = fac[i - 1] * i; fenjie[2].ps(2);fenjie[3].ps(3); rep1(i, 4, 9) { dfs(2, i,0,1); } rei(n); scanf("%s", s + 1); rep1(i, 1, n) temp[i] = s[i] - '0'; rep1(i,1,n) if (temp[i] > 1) { int len = fenjie[temp[i]].size(); rep1(j, 0, len-1) { final_ans[++num] = fenjie[temp[i]][j]; } } sort(final_ans + 1, final_ans + 1 + num, cmp); rep1(i, 1, num) printf("%d", final_ans[i]); puts(""); //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC); return 0;}
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/04-08/20143398.html