数字游戏

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1080 字

求[a,b]中各位数字之和能被N整除的正整数

一本通
练习

正文

/*
原题：数字游戏（一本通 5.3 练习 1，取模数）
题意：求 [a,b] 中各位数字之和能被 N 整除的正整数个数，多组询问（每组含 a,b,N）。
思路：数位 DP，state=(pos,rem,tight)，rem 为当前数字和 mod N。
     末态 rem==0 计数，答案 = f(b) - f(a-1)。
复杂度：时间 O(log10 b * N)，空间 O(log10 b * N)
易错点：N 最大 99，rem 取模后只到 N-1；f 含 0，区间相减自然排除 0。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N;
int dig[15];
ll memo[15][100][2];
int len;
ll dfs(int pos, int rem, bool tight){
    if(pos == len){
        return rem == 0 ? 1 : 0;
    }
    if(memo[pos][rem][tight] != -1) return memo[pos][rem][tight];
    ll ans = 0;
    int up = tight ? dig[pos] : 9;
    for(int d = 0; d <= up; d++){
        ans += dfs(pos + 1, (rem + d) % N, tight && d == up);
    }
    return memo[pos][rem][tight] = ans;
}
ll f(ll n){
    len = 0;
    ll t = n;
    while(t){
        dig[len++] = t % 10;
        t /= 10;
    }
    if(len == 0) dig[len++] = 0;
    reverse(dig, dig + len);
    memset(memo, -1, sizeof(memo));
    return dfs(0, 0, true);
}
int main(){
    ll a, b;
    while(cin >> a >> b >> N){
        cout << f(b) - f(a - 1) << "\n";
    }
    return 0;
}

数字游戏

正文

一本通·提高篇的其它内容