1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
|
using namespace std;
using LL = long long; const int maxn = 22; int digit[maxn]; LL dp[maxn][maxn]; LL L, R;
LL (int l, int mod, bool flag) { if(!flag && ~dp[l][mod]) return dp[l][mod]; if(l == 0) { if(mod % 9 == 0) return dp[l][mod] = 0; return dp[l][mod] = 1; } int pos = flag ? digit[l] : 9; LL ret = 0; for(int i = 0; i <= pos; i++) { if(i == 9) continue; ret += dfs(l-1, (mod*10+i)%9, flag&&(i==pos)); } if(!flag) dp[l][mod] = ret; return ret; }
LL f(LL x) { int tot = 0; while(x) { digit[++tot] = x % 10; x /= 10; } return dfs(tot, 0, true); }
signed main() { freopen("in", "r", stdin); freopen("out", "w", stdout); int T, _ = 1; scanf("%d", &T); memset(dp, -1, sizeof(dp)); while(T--) { scanf("%lld%lld",&L,&R); printf("Case #%d: %lldn", _++, f(R)-f(L-1)); } return 0; }
|
近期评论