题目链接:https://ac.nowcoder.com/acm/contest/163/J
题目大意:给定一个数N,求区间[1,N]中满足可以整除它各个数位之和的数的个数。(1 ≤ N ≤ 1012).
输入:
2
10
18
输出:
Case 1: 10
Case 2: 12
解题思路:比较简单的一道数位dp题,因为N的范围最大可为10的十二次方,即数位和的范围为[1,108],1-108的最小公倍数很大不可求,所以我们直接暴力枚举数位和为1-108的情况,然后利用数位dp求出合法数的个数就可以了。
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll n,dp[20][150][110]; int a[20],mod; ll dfs(int pos,int sta,int sum,int limit){ //sta为当前数模mod的值,sum为数位之和 if(pos==0) return sum==mod&&sta==0; //如果数位和刚好为mod且模sum刚好为0即合法 if(!limit&&dp[pos][sta][sum]!=-1) return dp[pos][sta][sum]; int up=limit?a[pos]:9; ll ans=0; for(int i=0;i<=up;i++){ if(i+sum>mod)break; //剪枝,数位和已经超过mod ans+=dfs(pos-1,(sta*10+i)%mod,sum+i,limit&&i==up); } if(!limit)dp[pos][sta][sum]=ans; return ans; } ll solve(ll x){ int pos=0; while(x){ a[++pos]=x%10; x/=10; } ll ans=0; int cnt=pos; for(int i=1;i<=9*cnt;i++){ //枚举数位和为i的情况 memset(dp,-1,sizeof(dp)); mod=i; ans+=dfs(pos,0,0,1); //搜索数位和为i的合法数的个数 } return ans; } int main(){ int t; scanf("%d",&t); int kase=0; while(t--){ scanf("%lld",&n); printf("Case %d: %lld\n",++kase,solve(n)); } return 0; }