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.
样例输入
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
",x)
#define pri2(x,y) printf("%d %d
",x,y)
#define pri3(x,y,z) printf("%d %d %d
",x,y,z)
#define prl(x) printf("%lld
",x)
#define prl2(x,y) printf("%lld %lld
",x,y)
#define prl3(x,y,z) printf("%lld %lld %lld
",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
",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
",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
",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
",cas++,a[i-1]);
break;
}
}
}
return 0;
}