Codeforces 55D Beautiful Number

Codeforces 55D Beautiful Number

a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits.

Input

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).

Output

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).

Sample test(s)

Input

11 9

Output

9

Input

112 15

Output

2

思路:

  1. 在mod中,有一个规律,X%a = X%(b*a)%a; <=> X%( lcm(1,2,...,9) = 2520)%lcm(d[i]) == 0;即可将数值直接降到2520以内;
  2. 同时一个mod后的数,还需要记录的就是lcm(d[i]),这样每次又计算出来的子结构就直接相加即可(指mod之后的数值以及lcm相同的数(这时就可以看成是一个数)),lcm总共只有48个,(2^3,3^2,5,7的组合 4*3*2*2);
  3. dp[i][j][k]: [i]: 高位为第i位,[j] : 在mod 2520之后的数值,[k]:记录下高位的lcm,由于直接来会MLE,所以离散化了(使用标号index[]);

代码思路参考了:AC_Von

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)= 0;i < (n);i++)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
typedef long long ll;
const int MOD = 2520;
ll dp[21][2520][50];
int d[21],index[MOD+5];
void init()
{
    for(int i = 1,tot = 0;i <= MOD;i++)
        if(MOD % i == 0)  index[i] = tot++;
    MS1(dp);
}
int lcm(int a,int b)
{
    return a/__gcd(a,b)*b;
}
ll dfs(int pos,int prev,int prelcm,int edge)
{
    if(pos == -1) return prev % prelcm?0:1; // ***
    ll ans = dp[pos][prev][index[prelcm]];
    if( !edge && ~ans) return ans;
    ans = 0;
    int e = edge ? d[pos]:9;
    for(int i = 0;i <= e;i++){
        int nowlcm = i ? lcm(prelcm,i) : prelcm;
        int nowv = (prev * 10 + i)%MOD;
        ans += dfs(pos - 1,nowv,nowlcm,edge && i == e);
    }
    if(!edge) dp[pos][prev][index[prelcm]] = ans;
    return ans;
}
ll query(ll n)
{
    MS0(d);int tot = 0;
    while(n){
        d[tot++] = n%10;
        n /= 10;
    }
    return dfs(tot - 1,0,1,1);
}
int main()
{
    init();
    int T;
    cin>>T;
    while(T--){
        ll l,r;
        scanf("%I64d%I64d",&l,&r);
        printf("%I64d\n",query(r) - query(l-1));
    }
}

时间: 01-28

Codeforces 55D Beautiful Number的相关文章

FZU2179/Codeforces 55D beautiful number 数位DP

题目大意: 求  1(m)到n直接有多少个数字x满足 x可以整出这个数字的每一位上的数字 思路: 整除每一位.只需要整除每一位的lcm即可 但是数字太大,dp状态怎么表示呢 发现 1~9的LCM 是2520 ....也就是说只要对这个数mod2520 剩下的余数能整除lcm就可以整除了.. 计数的时候还有一个技巧,具体见注释 此外这个题还卡常数了,预处理lcm才过了.. 代码如下: #include <iostream> #include <stdio.h> #include<

CodeForces 55D Beautiful numbers 数位DP+数学

题意大概是,判断一个正整数区间内有多少个整数能被它自身的每一个非零的数字整除. 因为每一个位置上的整数集s = {0,1,2,3,4,5,6,7,8,9} lcm(s) = 2520 现在有一个整数t是由s中一个或者多个数字构成的,记为abcde,显然t = a*10^4+b*10^3+c*10^2+d*10^1+e 要使得t能被a,b,c,d,e整除,必然有t % lcm(a,b,c,d,e) = 0 因为a,b,c,d,e去重之后一定是s的一个子集,所以lcm(s)一定是lcm(a,b,c,

Codeforces 55D. Beautiful numbers(数位DP,离散化)

Codeforces 55D. Beautiful numbers 题意 求[L,R]区间内有多少个数满足:该数能被其每一位数字都整除(如12,24,15等). 思路 一开始以为是数位DP的水题,觉得只需要记录搜到当前位出现了哪些数字作为状态即可,明显是假算法...感觉这是一道数位DP好题.可以这样思考:一个数要想被其各位数字分别都整除,等价于它被那些数字的LCM整除.因此记录当前位,当前数对(1~9的LCM)取模的结果,当前出现的数字的LCM这三个值作为状态才合理,即dp[pos][sum][

CodeForces 55D Beautiful numbers

Beautiful numbers 题目链接 Description Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. We will not argue with this and just

CodeForces 55D - Beautiful numbers - [数位DP+离散化]

题目链接:https://cn.vjudge.net/problem/CodeForces-55D Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. We will not argue with

CodeForces - 55D Beautiful numbers (数位DP)

Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. We will not argue with this and just count the quantity of beautiful num

CodeForces - 55D - Beautiful numbers(数位DP,离散化)

链接: https://vjudge.net/problem/CodeForces-55D 题意: Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. We will not argue with

CodeForces 55D Beautiful numbers(数位dp&amp;&amp;离散化)

题目链接:[kuangbin带你飞]专题十五 数位DP A - Beautiful numbers 题意 ps:第一道数位dp,题真好,虽然是参考大牛方法悟过才a,但仍收获不少. 求一个区间内的Beautiful numbers有多少个.Beautiful numbers指:一个数能整除所有组成它的非0数字. 例如15可以被1和5整除,所以15是Beautiful numbers. 思路 Beautiful numbers指:一个数能整除所有组成它的非0数字. 等同于 一个数能整除 所有组成它的

CodeForces 55D Beautiful numbers(数位dp+数学)

题目链接: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,