Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- set<int> prime;
- ll mem[17][9 * 17 + 1][2];
- bool isPrime(int n) {
- if (n < 2) return false;
- for (int i = 2; i * i <= n; i++) {
- if (n % i == 0) return false;
- }
- return true;
- }
- ll dp(string &s, int pos, int sum, bool lwr) {
- if (pos == (int) s.size()) return prime.count(sum);
- if (mem[pos][sum][lwr] != -1) return mem[pos][sum][lwr];
- ll ret = 0;
- for (int digit = 0; digit <= (lwr ? s[pos] - '0' : 9); digit++) {
- ret += dp(s, pos + 1, sum + digit, (lwr && digit == (s[pos] - '0')));
- }
- // cout << pos << ' ' << sum << ' ' << lwr << ' ' << ret << '\n';
- return mem[pos][sum][lwr] = ret;
- }
- int main() {
- cin.tie(0)->sync_with_stdio(0);
- for (int i = 2; i <= 9 * 17; i++) {
- if (isPrime(i)) prime.insert(i);
- }
- ll k;
- cin >> k;
- ll l = 2, r = 1e17, ans = -1;
- while (l <= r) {
- memset(mem, -1, sizeof(mem));
- ll m = (l + r) / 2;
- string s = to_string(m);
- if (dp(s, 0, 0, 1) >= k) {
- ans = m;
- r = m - 1;
- }
- else l = m + 1;
- }
- cout << ans << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement