Supreme Number

题目描述

A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.

Now lets define a number N as the supreme number if and only if each number made up of an non-empty subsequence of all the numeric digits of N must be either a prime number or 1.

For example, 17 is a supreme number because 1, 7, 17 are all prime numbers or 1, and 19 is not, because 9 is not a prime number.

Now you are given an integer N (2≤N≤10100), could you find the maximal supreme number that does not exceed N?

输入

In the first line, there is an integer T(T≤100000) indicating the numbers of test cases.

In the following T lines, there is an integer N (2≤N≤10100).

输出

For each test case print "Case #x: y", in which x is the order number of the test case and y is the answer.

样例输入

26100

样例输出

Case #1: 5Case #2: 73

题解

通过打表发现满足条件的最大数为317

坑点在于石油大把10^100写成10100

代码

#include
    
     using namespace std;#define rep(i,a,n) for(int i=a;i
     
      #define PLL pair
      
       #define PI acos(1.0)#define eps 1e-6#define inf 1e17#define INF 0x3f3f3f3f#define MOD 998244353#define mod 1e9+7#define N 1000005const int maxn=10000;// int prime[1000100]; //打表程序// bool book[1000100];// int top;// void isprime()// {//    memset(book, true, sizeof(book));//    book[1] = false;//    for(int i=2;i
       
        = 1000;i--)//   {//     if(book[i])//     {//       int temp = i;//       int a = temp%10;//       temp/=10;//       int b = temp%10;//       temp/=10;//       int c = temp%10;//       temp /=10;//       int d = temp;//       printf("%d %d %d %d\n",d,c,b,a);//       if(book[a] && book[b] && book[c]  && book[d]  && book[d*10+c] && book[d*10+b] && book[d*10+a] && book[c*10 + b] && book[c*10 + a] && book[b*10 + a] && book[d*100 + c*10 +b] && book[d*100 + c*10 +a] && book[d*100 + b*10 +a] && book[c*100 + b*10 +a])//       {//         printf("%d\n",i);//       }//     }//   }// }int a[100] = {1,2,3,5,7,11,13,17,23,31,37,53,71,73,113,131,137,173,311,317,10101};int main(){  int n;  int t;  sca(t);  int cas = 1;  string s;  while(t--)  {      // sca(n);      n = 0;      cin>>s;      if(s.length()>4)      {        printf("Case #%d: %d\n",cas++,317);        continue;      }      rep(i,0,s.length())      {        n = n*10+s[i]-'0';      }      rep(i,0,21)      {        if(n