ACM-ICPC 2018 沈阳赛区网络预赛 K Supreme Number(规律)

https://nanti.jisuanke.com/t/31452

题意

给出一个n (2 ≤ N ≤ 10100 )，找到最接近且小于n的一个数，这个数需要满足每位上的数字构成的集合的每个非空子集组成的数字是个素数或1。

分析

打表发现满足要求的数字很少。实际上因为一个数不能出现两次，而偶数不能存在。这样最后只有20个数符合要求。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
const int inf = 1e9+7;

int ans[20] = {1,2,3,5,7,11,13,17,23,31,37,53,71,73,113,131,137,173,311,317};
char s[110];
int main(){
#ifdef LOCAL
    freopen("in","r",stdin);
//    freopen("out.txt","w",stdout);
#endif // LOCAL
    int t, len;
    scanf("%d", &t);
    for(int _=1;_<=t;_++){
        scanf("%s", s);
        printf("Case #%d: ", _);
        len = strlen(s);
        if(len>3){
            printf("317
");
        }else{
            int tmp = 0;
            for(int i = 0;i<len;i++){
                tmp = tmp * 10 + (s[i]-'0');
            }
            int ANS = ans[0];
            for(int i = 0;i<20;i++){
                if(ans[i]<=tmp){
                    ANS = ans[i];
                }
            }
            printf("%d
", ANS);
        }


    }
    return 0;
}