CodeForces 55D Beautiful numbers(数位dp+数学)
2024-09-01 07:40:59
题目链接:http://codeforces.com/problemset/problem/55/D
题意:一个美丽数就是可以被它的每一位的数字整除的数。
给定一个区间,求美丽数的个数。
显然这是一道数位dp,就是满足一个数能被所有位数的lcm整除即可。
一般都会设dp[len][mod][LCM],mod表示余数,LCM表示前len位的lcm。
但是如果直接裸mod会很复杂,于是再想lcm{0,1,2,3,4,5,6,7,8,9}=2520;
而且lcm{a,b,c,d....}{a,b,c,d...表示各个位数)去重之后能被lcm{0,1,2....9}
整除。我们要求的是sum%lcm(a,b,c,d..}==0,所以只要满足
sum%lcm(0,1,2,...9}%lcm(a,b,c,d..}==0即可。于是mod就可以表示为
sum%lcm(0,1,2,...9}为多少。但是mod<=2520 && LCM<=2520这样
肯定存不下,于是要考虑如何处理LCM,毕竟很明显0~9的最大公倍数种类不会
超过48个。于是可以考虑一下离散化一下LCM,
if 2520 % num == 0 -> LCM[num]=temp++;
这样dp的三维就可以设为dp[20][2520][48];
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;
typedef long long ll;
const int mmax = 2520;
ll n , m , dp[20][mmax][50];
int temp , dig[20] , LCM[mmax + 10];
ll gcd(ll a , ll b) {
return b > 0 ? gcd(b , a % b) : a;
}
ll lcm(ll a , ll b) {
return a / gcd(a , b) * b;
}
void init() {
temp = 0;
for(int i = 1 ; i <= mmax ; i++) {
if(mmax % i == 0) {
LCM[i] = temp++;
}
else {
LCM[i] = 0;
}
}
}
ll dfs(int len , int count , int mod , int flag) {
if(!len) {
return mod % count == 0;
}
if(!flag && dp[len][mod][LCM[count]] != -1) {
return dp[len][mod][LCM[count]];
}
int t = flag ? dig[len] : 9;
ll sum = 0;
for(int i = 0 ; i <= t ; i++) {
int Nextmod = (mod * 10 + i) % mmax;
int Nextcount;
if(i == 0) {
Nextcount = count;
}
else {
Nextcount = (int)lcm(count , i);
}
sum += dfs(len - 1 , Nextcount , Nextmod , flag && i == t);
}
if(!flag)
dp[len][mod][LCM[count]] = sum;
return sum;
}
ll Gets(ll x) {
memset(dig , 0 , sizeof(dig));
int len = 0;
if(x == 0) {
dig[++len] = 0;
}
while(x) {
dig[++len] = x % 10;
x /= 10;
}
return dfs(len , 1 , 0 , 1);
}
int main() {
int t;
scanf("%d" , &t);
init();
memset(dp , -1 , sizeof(dp));
while(t--) {
scanf("%I64d%I64d" , &n , &m);
printf("%I64d\n" , Gets(m) - Gets(n - 1));
}
return 0;
}
最新文章
- Error:Execution failed for task &#39;:app:clean&#39;.
- Windows远程桌面打印机映射
- 原生js实现jquery库中部分事件的功能(jquery库封装二)
- Redis从基础命令到实战之有序集合类型(SortedSet)
- ajax页面加载进度条插件
- iOS开发UI篇—在UItableview中实现加载更多功能
- NYOJ 106背包问题
- svnChina的使用方法
- iOS开发:bitcode介绍和使用cocoapods出现“target overrides the `OTHER_LDFLAGS`……”的解决方案
- Hibernate Cascade &; Inverse
- DeepLearnToolbox使用总结
- DCL的失效:现实与初衷的背离
- 再叙ASM
- 你不知道的JavaScript--Item17 循环与prototype最后的几点小tips
- 你云我云•兄弟夜谈会 第二季 5G
- [学习笔记]利用e-debug和GetWindowTextA破解CM课件
- LOJ #6432. 「PKUSC2018」真实排名(组合数)
- hue中使用oozie的workflow执行mr
- git gitlab 部署
- 使用 xUnit 编写 ASP.NET Core WebAPI单元测试
热门文章
- 非web下的PowerMockito单元测试
- powershell小脚本--批量添加用户属性----导出登录时间
- 自练Eclipse搭建SSH全自动注解博客项目笔记
- 【Java例题】2.1复数类
- C# Winform 自定义控件——竖着的Navbar
- java学习-NIO(五)NIO学习总结以及NIO新特性介绍
- js动态添加<;tr>;<;td>;
- HTML文件上传与下载
- Linux安装配置Samba共享文件系统
- Vue + TypeScript + Element 搭建简洁时尚的博客网站及踩坑记