Code c++ Bài Tổng các chữ số trong đề thi OLP Miền Trung Tây Nguyên bảng Không chuyên vòng chung kết năm 2023

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


typedef long long ll;
typedef double db;
const int K = 1e6 + 5;
ll n, k, p[20];
ll dp[13][2][K], f[13][2][K];
int digit[13];

inline int sumdigit(ll x){
    int res = 0;
    while(x) res += x % 10, x /= 10;
    return res;
}

inline int len(ll x){
    int res = 0;
    while(x) ++res, x /= 10;
    return res;
}

inline int get(ll x, int row){
    return (x / p[row]) % 10;
}

void readip(){
    cin >> n >> k;
}

ll F(int i, bool t, int m){
    if (i < 0) return m == 0;
    if (f[i][t][m] != -1 && !t) return f[i][t][m];
    ll &res = f[i][t][m];
    res = 0;

    int lim = t ? digit[i] : 9;

    for(int d=0;d<=lim;d++)
        res += F(i - 1, t & (d == lim), (1LL * m * 10 + d) % k);
    return res;
}

ll Dp(int i, bool t, int m){
    if (i < 0) return 0;
    if (dp[i][t][m] != -1 && !t) return dp[i][t][m];
    ll &res = dp[i][t][m];
    res = 0;

    int lim = t ? digit[i] : 9;

    for(int d=0;d<=lim;d++){
        ll tmp = F(i - 1, t & (d == lim), (1LL * m * 10 + d) % k);
        res += 1LL * d * tmp;
        res += Dp(i - 1, t & (d == lim) , (1LL * m * 10 + d) % k);
    }
    return res;
}

void solve(){
    if (k > 1e5){
        ll res = 0;
        for (int i = 1; 1LL * i * k <= n; ++i)
            res += sumdigit(1LL * i * k);
        cout << res << endl;
        return;
    }
    memset(dp, -1, sizeof dp);
    memset(f, -1, sizeof f);

    for(int i=0;i<=12;i++) digit[i] = get(n,i);
    cout << Dp(len(n) - 1, 1, 0) << endl;
}

int main(){
 //   freopen("b.inp","r",stdin);
 //   freopen("b.out","w",stdout);
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    p[0] = 1;

    for(int i=1;i<=13;i++)
        p[i] = 10LL * p[i-1];
    int t = 2;

    while (t--){
        readip();
        solve();
    }
}