ural 1343. Fairy Tale

  1 /**
  2 Create By yzx - stupidboy
  3 */
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <cstdlib>
  7 #include <cmath>
  8 #include <deque>
  9 #include <vector>
 10 #include <queue>
 11 #include <iostream>
 12 #include <algorithm>
 13 #include <map>
 14 #include <set>
 15 #include <ctime>
 16 #include <iomanip>
 17 using namespace std;
 18 typedef long long LL;
 19 typedef double DB;
 20 #define For(i, s, t) for(int i = (s); i <= (t); i++)
 21 #define Ford(i, s, t) for(int i = (s); i >= (t); i--)
 22 #define Rep(i, t) for(int i = (0); i < (t); i++)
 23 #define Repn(i, t) for(int i = ((t)-1); i >= (0); i--)
 24 #define rep(i, x, t) for(int i = (x); i < (t); i++)
 25 #define MIT (2147483647)
 26 #define INF (1000000001)
 27 #define MLL (1000000000000000001LL)
 28 #define sz(x) ((int) (x).size())
 29 #define clr(x, y) memset(x, y, sizeof(x))
 30 #define puf push_front
 31 #define pub push_back
 32 #define pof pop_front
 33 #define pob pop_back
 34 #define ft first
 35 #define sd second
 36 #define mk make_pair
 37 inline void SetIO(string Name)
 38 {
 39     string Input = Name+".in",
 40     Output = Name+".out";
 41     freopen(Input.c_str(), "r", stdin),
 42     freopen(Output.c_str(), "w", stdout);
 43 }
 44 
 45 
 46 inline int Getint()
 47 {
 48     int Ret = 0;
 49     char Ch = ‘ ‘;
 50     bool Flag = 0;
 51     while(!(Ch >= ‘0‘ && Ch <= ‘9‘))
 52     {
 53         if(Ch == ‘-‘) Flag ^= 1;
 54         Ch = getchar();
 55     }
 56     while(Ch >= ‘0‘ && Ch <= ‘9‘)
 57     {
 58         Ret = Ret * 10 + Ch - ‘0‘;
 59         Ch = getchar();
 60     }
 61     return Flag ? -Ret : Ret;
 62 }
 63 
 64 const int N = 3200010;
 65 int Prime[N], Tot;
 66 bool Visit[N];
 67 int m;
 68 LL n, Fact[13];
 69 
 70 inline void getPrime()
 71 {
 72     For(i, 2, N - 1)
 73     {
 74         if(!Visit[i]) Prime[++Tot] = i;
 75         For(j, 1, Tot)
 76         {
 77             if(i * Prime[j] >= N) break;
 78             Visit[i * Prime[j]] = 1;
 79             if(i % Prime[j] == 0) break;
 80         }
 81     }
 82 }
 83 
 84 inline void Input()
 85 {
 86     getPrime();
 87     scanf("%d", &m);
 88     if(m) cin >> n;
 89 }
 90 
 91 inline bool isPrime(LL x)
 92 {
 93     if(x <= 1) return 0;
 94     For(i, 1, Tot)
 95     {
 96         if(x <= Prime[i]) break;
 97         if(x % Prime[i] == 0) return 0;
 98     }
 99     return 1;
100 }
101 
102 inline void Solve()
103 {
104     srand(time(0));
105     Fact[0] = 1;
106     For(i, 1, 12) Fact[i] = Fact[i - 1] * 10LL;
107 
108     LL Tmp = n * Fact[12 - m];
109     //isPrime(277717333835LL);
110     while(!isPrime(Tmp))
111     {
112         Tmp = n * Fact[12 - m];
113         For(i, m + 1, 12)
114             Tmp += (rand() % 10) * Fact[12 - i];
115     }
116 
117     printf("%012I64d\n", Tmp);
118 }
119 
120 int main()
121 {
122     #ifndef ONLINE_JUDGE
123     SetIO("F");
124     #endif
125     Input();
126     Solve();
127     return 0;
128 }