[codeforces 55]D. Beautiful numbers
[codeforces 55]D. Beautiful numbers
试题描述
输入
The first line of the input contains the number of cases t (1 ≤ t ≤ 10). Each of the next t lines contains two natural numbers li and ri(1 ≤ li ≤ ri ≤ 9 ·1018).
Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).
输出
Output should contain t numbers — answers to the queries, one number per line — quantities of beautiful numbers in given intervals (from li to ri, inclusively).
输入示例
输出示例
数据规模及约定
见“输入”
题解
“能同时被所有数位上的数字整除”等价于“能被所有数位上数字的最大公约数整除”。于是设 f[i][k][m] 表示一个 i 位的数,所有数字的最小公倍数等于 k,且这个数为 m。等等,状态 m 都知道这个数了,那 dp 个啥?别着急,我们一步步优化。
我们知道 lcm(1, 2, 3, 4, 5, 6, 7, 8, 9) = 2520(就是1~9的最小公倍数),那么对于刚才 m 的那一维状态是没有必要太大的,将这维状态对 2520 取个模就好了,即 m 表示这个数对 mod 2520 的值。
还有,1~9 这些数中,所有可能出现的最小公倍数只有 48 个(这个不妨读者自己写程序统计一下),所以离散一波 k 就变成最大只有 48 的数了。
最后状态数大概是:19 * 48 * 2520 = 2298240。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define LL long long LL read() {
LL x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
} #define maxn 21
#define maxm 2521
#define maxc 49
int Lcm[maxc], cl, id[maxm], Gcd[maxm][maxm];
bool tmp[maxm];
LL f[maxn][maxc][maxm], ten[maxn]; int gcd(int x, int y){ return !y ? x : gcd(y, x % y); } int get(int l, int x) {
int nl;
if(!x && !l) nl = 0;
if(x && l) nl = l * x / Gcd[l][x];
if(!x && l) nl = l;
if(x && !l) nl = x;
return nl;
} int num[maxn];
LL sum(LL x) {
int cnt = 0; LL tx = x;
while(x) num[++cnt] = x % 10, x /= 10;
LL ans = 0; int l = 1;
for(int i = cnt; i; i--) {
for(int j = 0; j < num[i]; j++) {
int nl = get(l, j);
for(int k = 0; k <= cl; k++) {
int nnl = get(nl, Lcm[k]);
LL t;
if(i < cnt) t = (tx / ten[i] * ten[i] + ten[i-1] * j) % 2520;
else t = ten[i-1] * j % 2520;
for(int m = 0; m < maxm - 1; m += nnl) {
int M = (m - t + 2520) % 2520; if(M < 0) continue;
if(f[i-1][k][M]) ans += f[i-1][k][M];
}
}
}
l = get(l, num[i]);
}
if(tx % l == 0) ans++;
return ans;
} int main() {
for(int i = 1; i < maxm; i++)
for(int j = 1; j < maxm; j++) Gcd[i][j] = gcd(i, j); tmp[1] = 1;
for(int j = 2; j <= 9; j++)
for(int x = maxm - 1; x; x--)
if(tmp[x]) tmp[x*j/Gcd[x][j]] = 1;
for(int i = 1; i < maxm; i++)
if(tmp[i]) Lcm[++cl] = i, id[i] = cl; ten[0] = 1;
for(int i = 1; i < maxn; i++) ten[i] = ten[i-1] * 10; f[0][0][0] = 1;
for(int j = 0; j <= 9; j++) f[1][id[j]][j] = 1;
for(int i = 1; i < maxn - 1; i++)
for(int k = 0; k <= cl; k++)
for(int m = 0; m < maxm; m++) if(f[i][k][m]) {
int l = Lcm[k];
for(int x = 0; x <= 9; x++) {
int nl = get(l, x);
f[i+1][id[nl]][(ten[i]*x+m)%2520] += f[i][k][m];
}
}
int T = read();
while(T--) {
LL l = read(), r = read();
printf("%I64d\n", sum(r) - sum(l - 1));
} return 0;
}
最新文章
- thusc2016游记&;&;滚粗记&;&;酱油记
- iOS App打包上架的流程
- 【CentOS】搭建Web服务器
- Codevs 2875 RY哥查字典
- ESRI Shapefiles (SHP)
- 依法使用Linux,反对Linux国产化
- 了解ASP.NET5 Web应用程序结构
- HTML5 Canvas | w3cschool菜鸟教程
- Ghostscript.Net Pdf 转 Image
- [原创]普通的MySQL多表连接查询
- python 自定义模块的发布和安装
- Python爬取淘宝店铺和评论
- SpringCloud入门之Spring Boot多环境配置切换指南
- vs不自动退出控制台程序的办法
- 07 zabbix之map拓扑标签中macro应用
- C# SpinLock实现
- torchvision.datasets.ImageFolder数据加载
- hydra 及相关示例
- 关于Android开发中使用的XML
- RHEL生命周期管理 -- Should I stay, or should I go?
热门文章
- C++中int,float,string,char*的转换(待续)
- VS2012 error C2664: “std::make_pair”:无法将左值绑定到右值引用
- 20145212 《Java程序设计》第4周学习总结
- Java反射机制<;1>;
- CV界的明星人物们
- 重写UILabler的sizeThatFits方法,需要触发两次才会有效果
- Python-面向对象编程(二)
- Yii2 执行流程
- MVC缓存OutPutCache学习笔记 (二) 缓存及时化VaryByCustom
- 详解FindBugs的各项检测器 .