fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4.  
  5. int t, a, b, k;
  6. string nString;
  7. int memo[10][2][90][90];
  8.  
  9. int dp(int index, bool tight, int sumMod, int sumDigitMod) {
  10. 	if (index == nString.size()) {
  11. 		if (sumMod == 0 && sumDigitMod == 0) {
  12. 			return 1;
  13. 		}
  14.  
  15. 		return 0;
  16. 	}
  17.  
  18. 	if (memo[index][tight][sumMod][sumDigitMod] != -1) {
  19. 		return memo[index][tight][sumMod][sumDigitMod];
  20. 	}
  21.  
  22. 	int limit = (tight ? nString[index] - '0' : 9);
  23. 	int result = 0;
  24. 	for (int digit = 0; digit <= limit; ++digit) {
  25. 		bool newTight = tight && (digit == limit);
  26. 		int newSumMod = (sumMod * 10 + digit) % k;
  27. 		int newSumDigitMod = (sumDigitMod + digit) % k;
  28. 		result += dp(index + 1, newTight, newSumMod, newSumDigitMod);
  29. 	}
  30.  
  31. 	memo[index][tight][sumMod][sumDigitMod] = result;
  32. 	return result;
  33. }
  34.  
  35. int f(int n) {
  36. 	if (k > 90) {
  37. 		return 0;
  38. 	}
  39. 	nString = to_string(n);
  40. 	memset(memo, -1, sizeof(memo));
  41. 	return dp(0, true, 0, 0);
  42. }
  43.  
  44. int main() {
  45. 	cin >> t;
  46. 	for (int i = 1; i <= t; ++i) {
  47. 		cin >> a >> b >> k;
  48. 		cout << "Case " << i << ": " << f(b) - f(a - 1) << '\n';
  49. 	}
  50.  
  51. 	return 0;
  52. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
3
1 20 1
1 20 2
1 1000 4
stdout
copy 
Case 1: 20
Case 2: 5
Case 3: 64
https://ideone.com/LtKlQ2
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

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!