CF515C Drazil and Factorial

CF515C Drazil and Factorial 题目链接

https://codeforces.com/problemset/problem/515/C

题目描述

Drazil正在和Varda一起玩数学游戏。

让我们定义正整数x作为其数字的阶乘的乘积。例如，F(135)=1!*3!*5!=720。

首先，他们选择一个十进制数a，a是一个由n个数字组成的数。此数字可能以前导零开头。然后他们要找到最大正数x，x满足以下两个条件：

1.x不包含任何数字0和数字1。

2.F(x)=F(a)。

帮朋友找到这样的号码。

输入输出格式
输入格式：
第一行包含一个整数n（1<=n<=15）。

第二行包含一个长度n的数字a。a至少有一位数字。数字a可能包含前导零。

输出格式：
输出满足上述条件的最大可能整数。在这个数字十进制表示中应该没有零和1。

解题思路

对样例分析时，对于阶乘相乘得到的数，肯定是可以拆分的阶乘数量越多越好。开始时我尝试不断地除于2!，后来发现最后剩下的数必须是其它阶乘的结果，这种贪心的思路是错误的。

在列出几个阶乘的结果以后，可以发现有些数阶乘是可以被更小更多的阶乘替代的，如下表所示：

2 ! = 2 2! = 2 2!=2
3 ! = 6 3! = 6 3!=6
4 ! = 3 ! ∗ 2 ! ∗ 2 ! 4! = 3! * 2! * 2! 4!=3!∗2!∗2!
5 ! = 120 5! =120 5!=120
6 ! = 5 ! ∗ 6 = 5 ! ∗ 3 ! 6! = 5! * 6 = 5! * 3! 6!=5!∗6=5!∗3!
7 ! = 5040 7! =5040 7!=5040
8 ! = 7 ! ∗ 8 = 7 ! ∗ 2 ! ∗ 2 ! ∗ 2 ! 8! = 7! *8 =7! * 2! * 2! * 2! 8!=7!∗8=7!∗2!∗2!∗2!
9 ! = 7 ! ∗ 72 = 7 ! ∗ 2 ∗ 36 = 7 ! ∗ 2 ! ∗ 3 ! ∗ 3 ! 9! =7! * 72 = 7! * 2 * 36 = 7! * 2! * 3! * 3! 9!=7!∗72=7!∗2∗36=7!∗2!∗3!∗3!

看着上面列出的表，我们可以得知不能拆分成其它阶乘的数字有{2,3,5,7}，正当我思考着如何把数拆成这4个数字阶乘相乘的形式，忽然想到原始数字也是通过阶乘的方式得到的，把得到的结果再进行拆分，多此一举了。

因此对于a来说，如果位数上为{2，3，5，7}，不需要拆分；如果是其它数字，按照上表拆分成更小的阶乘。最后从大小到输出统计的答案即可。

参考代码

#include 
using namespace std;
int ans[10];
int main(){
	int n;
	string str;
	cin>>n;
	cin>>str;
	for ( int i=0; i < n; i++)
		switch(str[i]){
			case '2': ans[2]++; break;
			case '3': ans[3]++; break;
			case '4': ans[2]+=2; ans[3]++; break;
			case '5': ans[5]++; break;
			case '6': ans[5]++; ans[3]++; break;
			case '7': ans[7]++; break;
			case '8': ans[7]++; ans[2]+=3; break;
			case '9': ans[7]++; ans[2]++; ans[3]+=2; break;
		}
		
	for ( int i=9; i >= 2; i--)
		for( int j=ans[i]; j>=1; j--)
			cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5693692.html