Advertisement
Dang_Quan_10_Tin

SNAD

Jan 22nd, 2021 (edited)
227
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.98 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. const int N = 9 * 19 + 2;
  6. ll x, y, n;
  7. ll dp[N][20][2];
  8. vector<ll> s;
  9.  
  10. /*
  11. Ý tưởng bài này như sau:
  12. Nếu gọi f(x) là số lượng số y mà y * (Tổng chữ số của y) <= x
  13. Thì đáp án sẽ là f(Y) - f(X - 1)
  14. --------------------------------
  15. Tính f(x):
  16. Gọi tích tổng quát là a * i với i là tổng các chữ số của a
  17. Ta duyệt i từ 1 tới 9 * 19 (Do có tối đa 19 chữ số)
  18. Để a * i <= x suy ra a <= x / i
  19. Đến đây ta qui về bài toán đếm số lượng số <= một số cho trước có tổng các chữ số cố định
  20. Đây là bài toán dp digit cơ bản trong bộ dp digit
  21. */
  22.  
  23. void Read()
  24. {
  25.     cin >> x >> y;
  26. }
  27.  
  28. // Cài dp = đệ qui có nhớ
  29.  
  30. ll f(int sum, int i, bool ok)
  31. {
  32.     // Nếu tổng các chữ số đã bị trừ hết
  33.     if (i == (int)s.size())
  34.         return dp[sum][i][ok] = (sum == 0);
  35.     // Nếu trạng thái đã duyệt qua
  36.     if (dp[sum][i][ok] != -1)
  37.         return dp[sum][i][ok];
  38.     ll &ans = dp[sum][i][ok];
  39.     ans = 0;
  40.     // Tất cả các trường hợp có thể
  41.     for (int j = 0; j <= 9; ++j)
  42.         if ((ok || (j <= s[i])) && sum >= j)
  43.             ans += f(sum - j, i + 1, ok || (j < s[i]));
  44.     return ans;
  45. }
  46.  
  47. ll Cal(ll x)
  48. {
  49.     ll ans(0);
  50.     // for tổng i
  51.     for (int i = 1; i <= 9 * 19; ++i)
  52.     {
  53.         ll t = x / i;
  54.         s.clear();
  55.         // Số x / i
  56.         while (t)
  57.         {
  58.             s.push_back(t % 10);
  59.             t /= 10;
  60.         }
  61.         reverse(s.begin(), s.end());
  62.         memset(dp, -1, sizeof dp);
  63.         ans += f(i, 0, 0);
  64.     }
  65.     return ans;
  66. }
  67.  
  68. void Solve()
  69. {
  70.     //cout << Cal(y) << " " << Cal(x - 1) << " ";
  71.     // f(y) - f(x - 1)
  72.     cout << Cal(y) - Cal(x - 1) << "\n";
  73. }
  74.  
  75. int32_t main()
  76. {
  77.     ios::sync_with_stdio(0);
  78.     cin.tie(0);
  79.     cout.tie(0);
  80.     int t;
  81.     cin >> t;
  82.     while (t--)
  83.     {
  84.        Read();
  85.        Solve();
  86.     }
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement