A prime number (or a prime) is a natural number greater than 11 that cannot be formed by multiplying two smaller natural numbers.
Now lets define a number NN as the supreme number if and only if each number made up of an non-empty subsequence of all the numeric digits of NN must be either a prime number or 11.
For example, 1717 is a supreme number because 11, 77, 1717 are all prime numbers or 11, and 1919 is not, because 99 is not a prime number.
Now you are given an integer N\ (2 \leq N \leq 10^{100})N (2≤N≤10100), could you find the maximal supreme number that does not exceed NN?
Input
In the first line, there is an integer T\ (T \leq 100000)T (T≤100000) indicating the numbers of test cases.
In the following TT lines, there is an integer N\ (2 \leq N \leq 10^{100})N (2≤N≤10100).
Output
For each test case print "Case #x: y"
, in which xxis the order number of the test case and yy is the answer.
样例输入
2 6 100
样例输出
Case #1: 5 Case #2: 73
题目来源
题意:一个supreme数是其的所有子集都是质数或者1(可以是不连续的子集),求小于n的最大的supreme数
分析:考虑单独的一个数是supreme数或1的有1,2,3,5,7,二位数是supreme数的有73,71,53,37,31,23,17,13,11,三位数是supreme数的有317,311,173,137,131,113,四位数没有supreme数
所以我们直接用个数组保存下来这些supreme数,然后看输入的数处于哪个范围就行
AC代码:
#include <map> #include <set> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <vector> #include <string> #include <bitset> #include <cstring> #include <iomanip> #include <iostream> #include <algorithm> #define ls (r<<1) #define rs (r<<1|1) #define debug(a) cout << #a << " " << a << endl using namespace std; typedef long long ll; const ll maxn = 1e5+10; const ll mod = 1e9+7; const double pi = acos(-1.0); const double eps = 1e-8; ll prime[] = {317,311,173,137,131,113,73,71,53,37,31,23,17,13,11,7,5,3,2,1}; int main() { ll T; cin >> T; for( ll cas = 1; cas <= T; cas ++ ) { string s; cin >> s; cout << "Case #" << cas << ": "; if( s.length() >= 4 ) { cout << 317 << endl; } else { ll sum = 0; for( ll i = 0; i < s.length(); i ++ ) { sum = sum*10 + (s[i]-'0'); } for( ll i = 0; i < 20; i ++ ) { if( sum >= prime[i] ) { cout << prime[i] << endl; break; } } } } return 0; }