时间戳

首页 > 解决方案 > 一个数中 x 的倍数

c++ - 一个数中 x 的倍数

问题描述

假设我们有一个从 l 到 r 的范围。我们被要求找到所有数字都是 x 的倍数的数字的计数。x 可以是 1 到 9 之间的任何数字。例如，取 l=20 和 r=40 和 x=2，则所需数字是 20、22、24、26、28、40，因为 x 的倍数是 0、2、4 ,6,8。

我为此编写了一个代码。它适用于一些测试用例。我不明白为什么它对大多数测试用例给出了错误的答案。

约束：1<=l<=r<=10^18。

我的代码：

  #include<bits/stdc++.h>
 using namespace std;
 #define ll long long int

 ll s1(vector<string> &v, ll N)
 {

ll i, j, n = v.size(), ans = 0;
string ss = "", s = "";

for (i = 0; i < n; i++)
{
    s += v[i];
}
ss = to_string(N);

ll d = ss.length(), f = 0, x = n - 1, y = 1;


for (i = 1; i < d; i++)
{
    if (i == 1)
    {
        ans += x;
        y = x;
        continue;
    }
    y = y * n;
    ans += y;
}
ll z = 0;

for (j = 0; j < d; j++)
{
    f = 0; 

    for (i = 0; i < s.length(); i++)
    {
        if (z == 0)
        {
            z++;
            continue;
        }
        
        if (s[i] < ss[j])
        {

            ans += pow(n, d - (j + 1));
            z++;
        }
        else if (s[i] == ss[j])
        {
            z++;
            f = 1;
            break;
        }
    }
    if (!f)
    {
        break;
    }
}
ans += f;

return and;
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin >> t;

while (t--)
{
    ll l, r;
    ll k, i, g;

    cin >> l >> r >> k;
    vector<ll> v1;

    ll x = 0;
    while (x <= 9)
    {
        v1.push_back(x);
        x = x + k;
    }

    vector<string> s;

    for (i = 0; i < v1.size(); i++)
    {
        g = v1[i];
        char c = g + '0';
        string d(1, c);
        s.push_back(d);
        //  cout << D[i] << " ";
    }

    cout << s1(s, r) - s1(s, l - 1) << '\n';

}

 }

谁能告诉我这个问题的更好逻辑？

标签： c++algorithmnumbers

解决方案

  1. 使用动态编程，我们可以编写一个函数，该函数f(x,d)为我们提供范围内的数字数量，[0,x]使得每个数字都是d
  2. dp 状态：[position in X][is our number prefix == X prefix?]
  3. 这将使用log10(X) * 2空间
  4. 启动状态明显[0][1]
  5. 然后我们只需填写 dp 表，使用递归特别容易，我们只需检查我们可以添加的下一个数字是什么，它包含所有条件
  6. 因此，如果我们删除常量，这种 dp 函数的总复杂度将是O(log10(X) * 2 * 10)或者仅仅是O(log N)
  7. 那么答案就是 f(R,x) - f(L-1,x)

示例代码（C++）：

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll dp[22][2]; //[position in X][is our number prefix == X prefix?]

ll do_dp(vector<int>&digits, int k, int pos = 0, bool isEq = true)
{
    if(pos >= digits.size())return 1;
    if(dp[pos][isEq] != -1)return dp[pos][isEq];

    dp[pos][isEq] = 0;
    for(int d = 0; d <= (isEq ? digits[pos] : 9); d++) //d is next digit
        if(d % k == 0) //multiple of k
        dp[pos][isEq] += do_dp(digits, k, pos+1, isEq && d == digits[pos]);

    return dp[pos][isEq];
}

ll solve(ll x, int k)
{
    vector<int>digits;
    while(x > 0){
        digits.push_back(x%10);
        x/=10;
    }
    reverse(digits.begin(),digits.end());
    memset(dp, -1, sizeof dp);
    return do_dp(digits, k);
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll t,l,r,k;
    cin>>t;
    while(t--)
    {
        cin>>l>>r>>k;
        cout<<solve(r,k) - solve(l-1,k)<<"\n";
    }
}

推荐阅读