fork download 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. vector<int> digit; 
  12.  
  13. vector<int> getDigit(ll N) {
  14. 	vector<int> ans; 
  15. 	for (; N > 0; N /= 10) ans.push_back(N % 10); 
  16. 	return ans; 
  17. }
  18.  
  19. bool isPrime[136];
  20.  
  21. void sieve() {
  22. 	for (int i = 2; i <= 135; i++) isPrime[i] = true;  
  23. 	for (int i = 2; i * i <= 135; i++) {
  24. 		if (isPrime[i]) {
  25. 			for (int j = i * i; j <= 135; j += i) isPrime[j] = false; 
  26. 		}
  27. 	}
  28. }
  29.  
  30. ll memo[16][2][3][136][136];
  31.  
  32. // Số cặp số của phần còn lại thoả mãn điều kiện và có "số nhớ" ở vị trí idx hiện tại là carry 
  33. // khi phần prefix ở trước vị trí idx mang theo điều kiện smaller 
  34. // và có tổng các chữ số của x là sum_digit_x, tổng các chữ số của y là sum_digit_y 
  35. ll dp(int idx, bool smaller, int carry, int sum_digit_x, int sum_digit_y) {
  36. 	if (idx == -1) {
  37. 		return (carry == 0 && isPrime[sum_digit_x] && isPrime[sum_digit_y]); 
  38. 	}
  39.  
  40. 	ll& ans = memo[idx][smaller][carry][sum_digit_x][sum_digit_y]; 
  41. 	if (ans != -1) return ans;  
  42.  
  43. 	ans = 0;  
  44. 	int max_digit = (smaller) ? 9 : digit[idx]; 
  45. 	for (int prev_carry = 0; prev_carry <= 2; prev_carry++) {
  46. 		for (int x_i = 0; x_i <= 9; x_i++) {
  47. 			for (int y_i = 0; y_i <= 9; y_i++) {
  48. 				int sum = x_i + 2 * y_i + prev_carry; 
  49. 				int i = sum % 10; 
  50. 				if (i > max_digit) continue; 
  51. 				if (sum / 10 != carry) continue; 
  52. 				ans += dp(idx - 1, smaller | (i < digit[idx]), prev_carry, sum_digit_x + x_i, sum_digit_y + y_i); 
  53. 			}
  54. 		}
  55. 	}
  56.  
  57. 	return ans; 
  58. }
  59.  
  60. ll solve(ll N) {
  61. 	digit = getDigit(N); 
  62. 	memset(memo, -1, sizeof memo); 
  63. 	return dp(digit.size() - 1, 0, 0, 0, 0); 
  64. }
  65.  
  66. int main() {
  67. 	ios::sync_with_stdio(false); 
  68. 	cin.tie(nullptr); 	
  69. 	sieve();   
  70.  
  71. 	ll N; 
  72. 	cin >> N; 
  73. 	ll ans = solve(N) - solve(N - 1);
  74. 	cout << ans << '\n'; 
  75. }
Success #stdin #stdout 0.01s 17428KB
comments (?)
stdin 
100
stdout 
7
https://ideone.com/NTxeNc
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!