2 条题解

  • 0
    @ 2025-10-8 17:04:47
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int N=30, M=210;
    int len; LL a[N], P, dp[N][M][M];
    LL dfs(int x, LL sum, int num, int lim){ //当前第几位,数本身,位数和,是否是上限
        if(x==0) return (sum==0 && num==P)? 1: 0; //sum=0代表能整除,num=P代表合法
        if(!lim && dp[x][sum][num]>=0) return dp[x][sum][num];
        LL res=0; int up=lim? a[x]: 9;
        for(int i=0; i<=up; i++){
            res+=dfs(x-1, (sum*10+i)%P, num+i, lim && (i==up));
        }
        if(!lim) dp[x][sum][num]=res;
        return res;
    }
    LL calc(LL x){
        len=0; LL res=0;
        while(x>0) a[++len]=x%10, x/=10;
        for(P=1; P<=len*9; P++){ //枚举位数总和
            memset(dp, -1, sizeof(dp));
            res+=dfs(len, 0, 0, 1);
        }
        return res;
    }
    int main(){
        //freopen("a.in", "r", stdin);
        LL a, b; scanf("%lld%lld", &a, &b);
        LL x=calc(b), y=calc(a-1);
        printf("%lld\n", x-y);
        return 0;
    }
    
    • 0
      @ 2025-10-8 17:04:34
      #include<bits/stdc++.h>
      using namespace std;
      typedef long long LL;
      const int N=30, M=210;
      int len; LL a[N], P, dp[N][M][M];
      LL dfs(int x, LL sum, int num, int lim){ //当前第几位,数本身,位数和,是否是上限
          if(x==0) return (sum==0 && num==P)? 1: 0; //sum=0代表能整除,num=P代表合法
          if(!lim && dp[x][sum][num]>=0) return dp[x][sum][num];
          LL res=0; int up=lim? a[x]: 9;
          for(int i=0; i<=up; i++){
              res+=dfs(x-1, (sum*10+i)%P, num+i, lim && (i==up));
          }
          if(!lim) dp[x][sum][num]=res;
          return res;
      }
      LL calc(LL x){
          len=0; LL res=0;
          while(x>0) a[++len]=x%10, x/=10;
          for(P=1; P<=len*9; P++){ //枚举位数总和
              memset(dp, -1, sizeof(dp));
              res+=dfs(len, 0, 0, 1);
          }
          return res;
      }
      int main(){
          //freopen("a.in", "r", stdin);
          LL a, b; scanf("%lld%lld", &a, &b);
          LL x=calc(b), y=calc(a-1);
          printf("%lld\n", x-y);
          return 0;
      }
      • 1

      信息

      ID
      3455
      时间
      3000ms
      内存
      128MiB
      难度
      5
      标签
      递交数
      34
      已通过
      14
      上传者