40分求助!!!
查看原帖
40分求助!!!
475143
gaojian2007楼主2022/11/22 11:15
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
long long l,r,mod;
long long x[25],dp[25][200][100];
long long dfs(int i,int pd,int sum,long long st){
    if(i==0){
        if(sum==mod&&st==0)
        return 1;
        return 0;
    }
    if(dp[i][sum][st]!=-1&&!pd){
        return dp[i][sum][st];
    }
    int ji=9;
    long long ans=0;
    if(pd)
    ji=x[i];
    for(int j=0;j<=ji;j++){
        ans+=dfs(i-1,pd&(j==ji),sum+j,(10ll*st+j)%mod);
    }
    if(!pd)
    dp[i][sum][st]=ans;
    return ans;
}
long long work(long long s){
    int cnt=0;
    while(s){
        x[++cnt]=s%10;
        s/=10;
    }
    long long ans=0;
    for(int i=1;i<=9*cnt;i++){
        memset(dp,-1,sizeof(dp));
        mod=i;
        ans+=dfs(cnt,1,0,0);
    }
    return ans;
}
int main(){
    scanf("%lld%lld",&l,&r);
    printf("%lld",work(r)-work(l-1));
}
2022/11/22 11:15
加载中...