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 X) {
  14. 	vector<int> ans; 
  15. 	for (; X > 0; X /= 10) ans.push_back(X % 10); 
  16. 	return ans; 
  17. }
  18.  
  19. ll memo[19][2][172]; 
  20.  
  21. // Số lượng số thoả mãn phần còn lại có tổng các chữ số = sum_digit
  22. // khi phần prefix ở trước vị trí idx mang theo điều kiện smaller
  23. ll dp(int idx, bool smaller, int sum_digit) {
  24. 	if (idx == -1) return (sum_digit == 0);
  25.  
  26. 	ll& ans = memo[idx][smaller][sum_digit]; 
  27. 	if (ans != -1) return ans; 
  28.  
  29. 	ans = 0;  
  30. 	int max_digit = (smaller) ? 9 : digit[idx]; 
  31. 	for (int i = 0; i <= max_digit; i++) {
  32. 		if (sum_digit - i >= 0) {
  33. 			ans += dp(idx - 1, smaller | (i < digit[idx]), sum_digit - i); 
  34. 		}
  35. 	}
  36.  
  37. 	return ans; 
  38. }
  39.  
  40. // Số lượng số <= X mà có tổng các chữ số = sum_digit
  41. ll solve(ll X, int sum_digit) {
  42. 	digit = getDigit(X);
  43. 	memset(memo, -1, sizeof memo); 
  44. 	return dp(digit.size() - 1, 0, sum_digit); 
  45. }
  46.  
  47. int main() {
  48. 	ios::sync_with_stdio(false); 
  49. 	cin.tie(nullptr); 	
  50. 	int T; cin >> T; 
  51. 	while (T--) {
  52. 		ll X, Y; 
  53. 		cin >> X >> Y; 
  54.  
  55. 		ll ans = 0; 
  56. 		for (int sum_digit = 1; sum_digit <= 171; sum_digit++) {
  57. 			ll L = (X + sum_digit - 1) / sum_digit; 
  58. 			ll R = Y / sum_digit; 
  59. 			ans += solve(R, sum_digit) - solve(L - 1, sum_digit); 
  60. 		} 
  61.  
  62. 		cout << ans << '\n'; 
  63. 	}
  64. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin 
1
20 30
stdout 
2
https://ideone.com/hKx9BY
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!