Beautiful numbers 数位DP +离散化

本文主要是介绍Beautiful numbers 数位DP +离散化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

题意

定义一种数字位美丽数，要求该数字能整除这个数的每一位数字(非零位)，求区间[l,r]内有多少符合条件的数

分析

光光给的数位dp的题目，难到自闭

首先一个数字如果符合美丽数的性质，那么他一定能整除他非零位的LCM
所以1 - 9的LCM为2520

所以，我们可以dfs，去搜索子树信息，对当前的数字 % 2520，最后判断能否整除LCM即可，符合答案加一

这里需要记忆话搜索一下，记录位数，当前的LCA，当前的数值大小，由于LCM不会超过100个，所以可以离散化一下（不是数论选手，不知道怎么推出来的）

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>using namespace std;
typedef long long ll;const int mod = 1e8+7;
ll dp[20][200][2600];
int p[2600];
int a[20];
int idx;int gcd(int a,int b){return (b>0)?gcd(b,a%b):a;}
int lcm(int x,int y){if(y == 0) return x;return x*y/gcd(x,y);}
int find(int x){if(!p[x]) p[x] = ++idx;return p[x];}ll dfs(int num,int sta,ll res,bool st){if(!num) return res % sta == 0;if(!st && dp[num][find(sta)][res]) return dp[num][find(sta)][res];ll ans = 0;int ed = st ? a[num] : 9;for(int i = 0;i <= ed;i++)ans += dfs(num - 1,lcm(sta,i),(res * 10 + i) % 2520,st && (i == ed));if(!st) dp[num][find(sta)][res] = ans;return ans;}ll solve(ll x){int num = 0;while(x){a[++num] = x % 10;x /= 10; }return dfs(num,1,0,1);
}int main(){int t;scanf("%d",&t);while(t--){ll n,m;scanf("%lld%lld",&n,&m);printf("%lld\n",solve(m) - solve(n - 1));}return 0;
}

这篇关于Beautiful numbers 数位DP +离散化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---