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.

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 l_i and r_i (1 ≤ l_i ≤ r_i ≤ 9 ·10¹⁸).

Output should contain t numbers — answers to the queries, one number per line — quantities of beautiful numbers in given intervals (from l_i to r_i, inclusively).

1
1 9

9

1
12 15

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));
    }
}