題目鏈接
題目描述
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.
樣例輸入
2
6
100樣例輸出
Case #1: 5
Case #2: 73題解
通過打表發現滿足條件的最大數為317
坑點在于石油大把10^100寫成10100
代碼
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define scac(x) scanf("%c",&x)
#define sca(x) scanf("%d",&x)
#define sca2(x,y) scanf("%d%d",&x,&y)
#define sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define scl(x) scanf("%lld",&x)
#define scl2(x,y) scanf("%lld%lld",&x,&y)
#define scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define pri(x) printf("%d\n",x)
#define pri2(x,y) printf("%d %d\n",x,y)
#define pri3(x,y,z) printf("%d %d %d\n",x,y,z)
#define prl(x) printf("%lld\n",x)
#define prl2(x,y) printf("%lld %lld\n",x,y)
#define prl3(x,y,z) printf("%lld %lld %lld\n",x,y,z)
#define ll long long
#define LL long long
#define pb push_back
#define mp make_pair
#define P pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(1.0)
#define eps 1e-6
#define inf 1e17
#define INF 0x3f3f3f3f
#define MOD 998244353
#define mod 1e9+7
#define N 1000005
const 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<maxn;i++)
// {
// if(book[i])
// {
// for(int j=i+i;j<maxn;j+=i)
// {
// book[j] = false;
// }
// }
// }
// for(int i=2;i<=maxn;i++)
// {
// if(book[i])
// {
// prime[++top] = i;
// }
// }
// }
// int main()
// {
// int n;
// isprime();
// book[1] = true;
// for(int i = 10000; 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<a[i]){printf("Case #%d: %d\n",cas++,a[i-1]);break;}}}return 0;
}:CSS3之我觀)
