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，预处理以下就好了。

代码

#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;
}

打表代码

#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