一、题目

1、题目描述

Let A=∑ni=1ai∗10n−i(1≤ai≤9)(n is the number of A's digits). We call A as “beautiful number” if and only if a[i]≥a[i+1] when 1≤i<n and a[i] mod a[j]=0 when 1≤i≤n,i<j≤n(Such as 931 is a "beautiful number" while 87 isn't).
Could you tell me the number of “beautiful number” in the interval [L,R](including L and R)?

2、输入输出

2.1输入

The fist line contains a single integer T(about 100), indicating the number of cases.
Each test case begins with two integers L,R(1≤L≤R≤109).

2 1 11 999999993 999999999

2.2输出

For each case, output an integer means the number of “beautiful number”.

10 2

3、原题链接

Problem - 5179 (hdu.edu.cn)

二、解题报告

1、思路分析

美丽数要求数位从高位到低位非升序，然后要求高位跟任意一位比它低的位取余为0

数位dp处理非升序很容易，那么怎么处理第二个条件呢？

我们根据基础数论的知识b ≡ 0 (mod c) ，a ≡ 0 (mod b)，则a ≡ 0 (mod c)，发现我们只要让前一位的因数作为下一位即可

所以我们用0~9的数字作为状态即可

2、复杂度

时间复杂度：O(nlogn) 空间复杂度：O(nlogn)

3、代码详解

​

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <functional>
using namespace std;
const int N = 10;
int f[N][N], d[N];int dfs(int n, int pre, bool lim, bool zero)
{if (!n)return 1;if (lim && !zero && ~f[n][pre])return f[n][pre];int res = 0, ceil = lim ? 9 : d[n];for (int i = 0; i <= ceil; i++)if (zero)res += dfs(n - 1, i, lim || i < ceil, !i);else if (i && i <= pre && pre % i == 0)res += dfs(n - 1, i, lim || i < ceil, 0);if (lim && !zero)return f[n][pre] = res;return res;
}void solve()
{int a, b, i = 0;cin >> a >> b;a--;while (b)d[++i] = b % 10, b /= 10;int r = dfs(i, 0, false, true);i = 0;while (a)d[++i] = a % 10, a /= 10;int l = dfs(i, 0, false, true);cout << r - l << '\n';
}int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);// freopen("in.txt", "r", stdin);int _ = 1;cin >> _, memset(f, -1, sizeof(f));while (_--)solve();return 0;
}