2018-ACM-ICPC沈阳网络预赛K题-Supreme Number

Supreme Number

问答

  • 26.7%
  • 1000ms
  • 131072K

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 xx is the order number of the test case and yy is the answer.

样例输入复制

1
2
3
2
6
100

样例输出复制

1
2
Case #1: 5
Case #2: 73

题目来源

ACM-ICPC 2018 沈阳赛区网络预赛

题解

非空子序列必须为素数,那么每一位就只能由1,2,3,5,7组成,且除了1以外其他只能出现一次,那么最后算上1就只剩下20个数了,1,2,3,5,7,11,13,17,23,31,37,53,71,73,113,131,137,173,311,317,预处理以下就好了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<cstdio>
using namespace std;
int pri[19] = {2,3,5,7,11,13,17,23,31,37,53,71,73,113,131,137,173,311,317};
int read()
{
char ch=' ';
int ans=0;
while(ch<'0' || ch>'9')
ch=getchar();
while(ch<='9' && ch>='0')
{
if(ans<100000)
ans=ans*10+ch-'0';
ch=getchar();
}
return ans;
}
int main()
{
int t;
cin>>t;
for(int aaa=1;aaa<=t;aaa++){
int ans = read();
int i;

for(i = 0;i<19;i++){
if(pri[i]>ans){
cout<<"Case #"<<aaa<<": "<<pri[i-1]<<endl;
break;
}
}
if(i==19)
cout<<"Case #"<<aaa<<": "<<pri[18]<<endl;
}
return 0;
}

打表代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<sstream>
using namespace std;
#define N 10000000
int h=0;
bool p[N];
int prime[N];
bool dfs(int x){
if(p[x]==false)
return false;
int c = 1;
while(c<x){
c*=10;
if(p[x%c]==false)
return false;

if(c>x)
break;
int tmp = x;
while(tmp){
if(p[tmp]==false)
return false;
if(p[tmp%c]==false)
return false;
tmp/=c;
if(!tmp)
break;
if(dfs(tmp)==false)
return false;
}
}
return true;
}

void db()
{
memset(p,true,sizeof(p));
p[0] = false;
for(int i=2;i<N;i++)
{
if(p[i]==false)
continue;
for(int j=2;i*j<N;j++)
{
p[i*j]=false;
}
if(!dfs(i))
p[i] = false;
if(p[i]==true)
{
prime[h++]=i;
}
}
}
int main()
{
db();
int n; //打印前n个质数
for(int i=0;i<=h;i++)
cout<<prime[i]<<",";
return 0;
}
//2,3,5,7,11,13,17,23,31,37,53,71,73,113,131,137,173,311,317

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!