本文主要是介绍hihocoder1791 幸运数字（数位dp） 也是The 2018 ACM-ICPC上海大（家）都会赛 J Beautiful Numbers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://hihocoder.com/problemset/problem/1791
题目求的是1-n中有多少个数能够整除它自己各数位上的数之和。
因为n的范围到1e12
所以这道题中各数位相加的和最大也是99
所以我们可以枚举1-99，求1-n中有多少数各数位和为i且能整除i ，
就和那道B-Number一样了，只不过是进行99次数位dp而已。
#include<bits/stdc++.h>
using namespace std;
int mod;
long long n;
int a[22];
long long dp[22][109][150];long long dfs(int pos, int sum, int remind, int limit)
{if(pos==-1)return sum==0&&remind==0;if(!limit&&dp[pos][sum][remind]!=-1) return dp[pos][sum][remind];int to;if(limit)to=a[pos];else to=9;long long ans=0;for(int i=0;i<=to;i++) if(i>sum)break;else ans+=dfs(pos-1,sum-i,(remind*10+i)%mod,limit&&i==a[pos]);if(!limit) dp[pos][sum][remind]=ans;return ans;
}long long solve(long long x)
{int cnt=0;while(x){a[cnt++]=x%10;x/=10;}long long ans=0;for(int i=1;i<=9*cnt;i++){mod=i; memset(dp,-1,sizeof(dp));ans+=dfs(cnt-1,i,0,1);}return ans;
}int main()
{while(cin>>n){cout<<solve(n)<<endl;}
}
这篇关于hihocoder1791 幸运数字（数位dp） 也是The 2018 ACM-ICPC上海大（家）都会赛 J Beautiful Numbers的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
