2 条题解
-
0
#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
#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
- 上传者