Codeforces Round #741 Scenes From a Memory 题解 (Java/C++)

题解

首先,显而易见的,如果原数中出现了1,4,6,8,9这几个数。则其他数都可以被删掉,只留这一位即可。

于是我们只剩下2,3,5,7。我们可以很容易的已发现,如果要构造出质数,必然有下列性质:
1. 每个数最多只能出现1次,否则一定可以构成被11整除的数。
2. 2和5一定不能同时出现,否则25和52都是合数。
3. 2和7不能同时出现,否则一定能被3整除。
4. 5和7不能同时出现,否则一定能被3整除。

我们发现如果用这些数字组成两位数,且这个两位数是质数的情况有且仅有,23,53,37,73。

接着我们再考虑构成三位数的情况。不难发现,构成的3位数一定是合数,或者可以再进一步删除数字。

综上,我们只需要依次枚举所有可以构成的三位以内的数即可。

代码

Java

Submission #127463690 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #127463771 - Codeforces
Codeforces. Programming competitions and contests, programming community