一个数是美丽的，当且仅当其可以被其所有的非0数位整除。求在区间[a,b]中有多少数是美丽的。
a,b<=10^18
这道题很明显是数位DP的分格，f[i][j][k][sta]表示前i个数，取值是否贴紧，前i个数的值%2520的值，前i个数的lcm(这里用离散化存），的方案数，答案就是count(b)-count(a-1);
还有数位DP中的技巧就是加上一个状态j表示是否贴紧。
666HQ的代码
#include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<cstring> using namespace std; #define ll long long ll pow10[20],Pow[20],dp[20][2][2520][50]; int num[20],flcm[512],Map[2521],Map2[50],tot; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int lcm(int a,int b) { if (a==0) return b; else if (b==0) return a; else return a/gcd(a,b)*b; } ll solve(ll x) { int len; ll ans=0; if (x==1e18) ans=1,x--; for (len=0;len<=18 && pow10[len]<=x;len++); for (int i=len;i>0;i--) num[i]=x%pow10[len-i+1]/pow10[len-i]; memset(dp,0,sizeof(dp)); dp[0][1][0][0]=1; for (int i=0;i<=len;i++) for (int j=0;j<2;j++) for (int k=0;k<2520;k++) for (int l=0;l<tot;l++) { ll p=dp[i][j][k][l]; int pp=Map2[l]; if (!p) continue; if (i==len) { if (k % pp==0) ans+=p; continue; } if (j==0) { for (int q=0;q<=9;q++) dp[i+1][0][(k+q*Pow[len-i-1])%2520][Map[lcm(pp,q)]]+=p; } else { for (int q=0;q<num[i+1];q++) dp[i+1][0][(k+q*Pow[len-i-1])%2520][Map[lcm(pp,q)]]+=p; dp[i+1][1][(k+num[i+1]*Pow[len-i-1])%2520][Map[lcm(pp,num[i+1])]]+=p; } } return ans; } void prepare() { pow10[0]=Pow[0]=1; for (int i=1;i<=18;i++) pow10[i]=pow10[i-1]*10,Pow[i]=pow10[i]%2520; for (int i=1;i<(1<<9);i++) for (int j=1;j<=9;j++) if (i & (1<<j-1)) flcm[i]=lcm(flcm[i-(1<<j-1)],j); for (int i=1;i<(1<<9);i++) if (!Map[flcm[i]]) Map[flcm[i]]=tot++,Map2[tot-1]=flcm[i]; } int main() { freopen("number.in ","r",stdin); freopen("number.out","w",stdout); prepare(); int T; scanf("%d",&T); while (T--) { ll a,b; scanf("%lld%lld",&a,&b); printf("%lld ",solve(b)-solve(a-1)); } return 0; }