[Codeforces-div.1 55D] Beautiful numbers

试题分析

还是离散化。。。\(f_{i,j,k}\)表示i位，gcd为j，余数为k。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

#define LL long long

inline LL read(){

    LL x=0,f=1; char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

    for(;isdigit(c);c=getchar()) x=x*10+c-'0';

    return x*f;

}

const LL MAXN = 100010;

const LL INF = 2147483600;

LL sta[MAXN+1]={0,1,2,3,4,5,6,7,8,9,10,12,14,15,18,20,21,24,28,30,35,36,40,42,45,56,60,63,70,72,84,90,105,120,126,140,168,180,210,252,280,315,360,420,504,630,840,1260,2520},top;

inline LL gcd(LL a,LL b){

    return (!b?a:gcd(b,a%b));

}

inline LL LCM(LL a,LL b){

    if(!a||!b) return b|a;

    return a*b/gcd(a,b);

}

LL f[21][50][2600];

LL cnt; LL str[MAXN+1],num[MAXN+1];

inline LL dfs(LL i,LL j,LL k,LL g){

    if(i==0) return j&&(k%sta[j]==0);

    if(!g && ~f[i][j][k]) return f[i][j][k];

    LL ans=0; for(LL l=0;l<=(g?str[i]:9);l++){

        LL x=LCM(sta[j],l);

        ans+=dfs(i-1,num[x],(k*10%2520+l)%2520,g&(str[i]==l));

    } return (g?ans:f[i][j][k]=ans);

}

inline LL init(LL x){

    cnt=0; while(x) str[++cnt]=x%10,x/=10;

    return dfs(cnt,0,0,1);

}

LL T;

int main(){

    //freopen(".in","r",stdin);

    memset(f,-1,sizeof(f));

    T=read(); for(LL i=1;i<49;i++) num[sta[i]]=i;

    while(T--){

        LL L=read(),R=read(); LL ans=0;

        ans+=init(R); ans-=init(L-1);

        printf("%lld\n",ans);

    }

    return 0;

}