Advertisement
tuki2501

solution_uit_55_180.cpp

Oct 1st, 2022
851
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.19 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. set<int> prime;
  7. ll mem[17][9 * 17 + 1][2];
  8.  
  9. bool isPrime(int n) {
  10.     if (n < 2) return false;
  11.     for (int i = 2; i * i <= n; i++) {
  12.         if (n % i == 0) return false;
  13.     }
  14.     return true;
  15. }
  16.  
  17. ll dp(string &s, int pos, int sum, bool lwr) {
  18.     if (pos == (int) s.size()) return prime.count(sum);
  19.     if (mem[pos][sum][lwr] != -1) return mem[pos][sum][lwr];
  20.     ll ret = 0;
  21.     for (int digit = 0; digit <= (lwr ? s[pos] - '0' : 9); digit++) {
  22.         ret += dp(s, pos + 1, sum + digit, (lwr && digit == (s[pos] - '0')));
  23.     }
  24.     // cout << pos << ' ' << sum << ' ' << lwr << ' ' << ret << '\n';
  25.     return mem[pos][sum][lwr] = ret;
  26. }
  27.  
  28. int main() {
  29.     cin.tie(0)->sync_with_stdio(0);
  30.     for (int i = 2; i <= 9 * 17; i++) {
  31.         if (isPrime(i)) prime.insert(i);
  32.     }
  33.     ll k;
  34.     cin >> k;
  35.     ll l = 2, r = 1e17, ans = -1;
  36.     while (l <= r) {
  37.         memset(mem, -1, sizeof(mem));
  38.         ll m = (l + r) / 2;
  39.         string s = to_string(m);
  40.         if (dp(s, 0, 0, 1) >= k) {
  41.             ans = m;
  42.             r = m - 1;
  43.         }
  44.         else l = m + 1;
  45.     }
  46.     cout << ans << '\n';
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement