# F. 質數家族 (primeconn)

Oct 5th, 2022
601
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. using namespace std;
3.
4. const int maxc = 1E7;
5.
6. bitset<maxc> isprime;
7. vector<int> p;
8.
9. int R(int x) {return x ^ p[x] ? p[x] = R(p[x]) : x;}
10. int U(int x, int y) {x = R(x), y = R(y); return x ^ y ? p[x] = y, 1 : 0;}
11.
12. int main() {
13.     ios_base::sync_with_stdio(0), cin.tie(0);
14.
15.     int N; cin >> N;
16.     if (N == maxc) --N;
17.
18.     p.resize(N+1), iota(begin(p), end(p), 0);
19.
20.     isprime.set();
21.     isprime[0] = isprime[1] = 0;
22.     for (int i = 2; i*i <= N; ++i) {
23.         if (!isprime[i]) continue;
24.         for (int j = i*i; j <= N; j += i) isprime[j] = 0;
25.     }
26.
27.     int64_t ans = 0;
28.     for (int i = 2; i <= N; ++i) {
29.         if (!isprime[i]) continue;
30.         // cerr << "isprime: " << i << "\n";
31.         string num = to_string(i);
32.         int len = num.size();
33.         for (int j = len-1, k = 1; j >= 0; --j, k *= 10) {
34.             for (int d = 1, val = i-k; d <= num[j]-'0'; ++d, val -= k) {
35.                 if (!j and i >= 10 and num[1] == '0' and d == num[0]-'0') continue;
36.                 if (isprime[val]) U(i, val); //, cerr << "  " << i << ", " << val << "\n";
37.             }
38.         }
39.         if (R(i) != R(2)) ans += i;
40.     }
41.     cout << ans << "\n";
42.
43.     return 0;
44. }
45.