fork download
copy 
  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. ll memo[15][2][126][127]; 
  20.  
  21. // r là số dư của phần prefix khi mod cho target_sum_digit
  22. ll dp(int idx, bool smaller, int r, int sum_digit, int target_sum_digit) {
  23. 	if (idx == -1) return (r == 0 && sum_digit == target_sum_digit); 
  24.  
  25. 	ll& ans = memo[idx][smaller][r][sum_digit]; 
  26. 	if (ans != -1) return ans; 
  27.  
  28. 	ans = 0; 
  29. 	int max_digit = (smaller) ? 9 : digit[idx];
  30. 	for (int i = 0; i <= max_digit; i++) {
  31. 		if (sum_digit + i <= target_sum_digit) {
  32. 			ans += dp(idx - 1, smaller | (i < digit[idx]), (r * 10 + i) % target_sum_digit, sum_digit + i, target_sum_digit); 
  33. 		}
  34. 	}
  35.  
  36. 	return ans; 
  37. }
  38.  
  39. ll solve(ll N, int target_sum_digit) {
  40. 	digit = getDigit(N); 
  41. 	memset(memo, -1, sizeof memo); 
  42. 	return dp(digit.size() - 1, 0, 0, 0, target_sum_digit); 
  43. }
  44.  
  45. int main() {
  46. 	ios::sync_with_stdio(false); 
  47. 	cin.tie(nullptr); 	
  48. 	ll N; 
  49. 	cin >> N; 
  50. 	ll ans = 0;  
  51. 	for (int sum_digit = 1; sum_digit <= 126; sum_digit++) {
  52. 		ans += solve(N, sum_digit); 
  53. 	}
  54.  
  55. 	cout << ans << '\n'; 
  56. }
  57.  
Success #stdin #stdout 0.02s 7340KB
comments (?)
stdin
copy 
20
stdout
copy 
13
https://ideone.com/8UQw0Y
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!