CodeForces 55D

tiberius 2019-08-30 原文

题意略。

思路：

本题可以说是醉翁之意不在酒了。要解开本题有几个关键点：

1.意识到数X = An An-1 An-2 An-3 …. A2 A1能被{An,An-1,An-2,….,A1}这n个数整除的充要条件是lcm(An,An-1,An-2,….,A1) | X。

2.要知道1~9这9个数进行组合最大的lcm是2520，而且组合出的lcm个数有限，最多48个。

3.我们为了判断这个数能否被它的所有数位整除，我们还需要这个数的值，显然要记录值是不可能的，其实我们只需记录它对2520的模即可。

因为所有的lcm都是2520的因子，所以我们用mod 2520的值来表示当前已经摆好组成的值，到了最后pos == -1的时候，我们再把当前的值mod 当前若干数位组合好的lcm，看看mod lcm 是不是等于0。

如果等于0，则是合格的解。

4.不用考虑前导0的影响。因为在 !limit 的前提下 1111[ ][ ] 与 [ ][ ]是一样的，对当前组合好的lcm不会产生影响。

代码附上：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn0 = 20;
const int maxn1 = 3000;
const int maxn2 = 50;
const int mod = 2520;

int a[maxn0],tail,T;
LL dp[maxn0][maxn2][maxn1],l,r;
int mp[maxn1],store[maxn1],t;

int gcd(int a,int b){
    return b == 0 ? a : gcd(b,a % b);
} 
int lcm(int a,int b){
    int d = gcd(a,b);
    return a / d * b;
}
void process(LL x){
    tail = 0;
    while(x){
        a[tail++] = int(x % 10);
        x /= 10;
    }
}
LL dfs(int pos,int Lcm,int remainder,bool limit){
    if(pos == -1 && remainder % store[Lcm] == 0) return 1;
    if(pos == -1 && remainder % store[Lcm] != 0) return 0;
    if(!limit && dp[pos][Lcm][remainder] != -1) return dp[pos][Lcm][remainder];
    
    int up = limit ? a[pos] : 9;
    LL ret = 0;
    for(int i = 0;i <= up;++i){
        int truelcm = store[Lcm];
        int ntruelcm = i == 0 ? truelcm : lcm(truelcm,i);
        int nlcm = mp[ntruelcm];
        int nremainder = (remainder * 10 + i) % mod;
        ret += dfs(pos - 1,nlcm,nremainder,limit && i == up);
    }
    if(!limit) dp[pos][Lcm][remainder] = ret;
    return ret;
}
void prepare(){
    int total = (1<<9);
    for(int i = 1;i < total;++i){
        int temp = 1;
        for(int j = 0;j < 9;++j){
            if(((i>>j) & 1) == 0) continue;
            temp = lcm(temp,(j + 1));
        }
        store[t++] = temp;
    }
    sort(store,store + t);
    t = unique(store,store + t) - store;
    for(int i = 0;i < t;++i){
        mp[store[i]] = i;
    }
}

int main(){
    prepare();
    memset(dp,-1,sizeof(dp));
    scanf("%d",&T);
    while(T--){
        scanf("%I64d%I64d",&l,&r);
        
        process(l - 1);
        LL ans0 = dfs(tail - 1,0,0,true);
        
        process(r);
        LL ans1 = dfs(tail - 1,0,0,true);
        
        printf("%I64d\n",ans1 - ans0);
    }
    return 0;
}