Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- const int N = 9 * 19 + 2;
- ll x, y, n;
- ll dp[N][20][2];
- vector<ll> s;
- /*
- Ý tưởng bài này như sau:
- Nếu gọi f(x) là số lượng số y mà y * (Tổng chữ số của y) <= x
- Thì đáp án sẽ là f(Y) - f(X - 1)
- --------------------------------
- Tính f(x):
- Gọi tích tổng quát là a * i với i là tổng các chữ số của a
- Ta duyệt i từ 1 tới 9 * 19 (Do có tối đa 19 chữ số)
- Để a * i <= x suy ra a <= x / i
- Đế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
- Đây là bài toán dp digit cơ bản trong bộ dp digit
- */
- void Read()
- {
- cin >> x >> y;
- }
- // Cài dp = đệ qui có nhớ
- ll f(int sum, int i, bool ok)
- {
- // Nếu tổng các chữ số đã bị trừ hết
- if (i == (int)s.size())
- return dp[sum][i][ok] = (sum == 0);
- // Nếu trạng thái đã duyệt qua
- if (dp[sum][i][ok] != -1)
- return dp[sum][i][ok];
- ll &ans = dp[sum][i][ok];
- ans = 0;
- // Tất cả các trường hợp có thể
- for (int j = 0; j <= 9; ++j)
- if ((ok || (j <= s[i])) && sum >= j)
- ans += f(sum - j, i + 1, ok || (j < s[i]));
- return ans;
- }
- ll Cal(ll x)
- {
- ll ans(0);
- // for tổng i
- for (int i = 1; i <= 9 * 19; ++i)
- {
- ll t = x / i;
- s.clear();
- // Số x / i
- while (t)
- {
- s.push_back(t % 10);
- t /= 10;
- }
- reverse(s.begin(), s.end());
- memset(dp, -1, sizeof dp);
- ans += f(i, 0, 0);
- }
- return ans;
- }
- void Solve()
- {
- //cout << Cal(y) << " " << Cal(x - 1) << " ";
- // f(y) - f(x - 1)
- cout << Cal(y) - Cal(x - 1) << "\n";
- }
- int32_t main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int t;
- cin >> t;
- while (t--)
- {
- Read();
- Solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement