题目链接：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[][][];
int a[],mod;
ll dfs(int pos,int sta,int sum,int limit){ //sta为当前数模mod的值，sum为数位之和
if(pos==)
return sum==mod&&sta==; //如果数位和刚好为mod且模sum刚好为0即合法
if(!limit&&dp[pos][sta][sum]!=-)
return dp[pos][sta][sum];
int up=limit?a[pos]:;
ll ans=;
for(int i=;i<=up;i++){
if(i+sum>mod)break; //剪枝，数位和已经超过mod
ans+=dfs(pos-,(sta*+i)%mod,sum+i,limit&&i==up);
}
if(!limit)dp[pos][sta][sum]=ans;
return ans;
}
ll solve(ll x){
int pos=;
while(x){
a[++pos]=x%;
x/=;
}
ll ans=;
int cnt=pos;
for(int i=;i<=*cnt;i++){ //枚举数位和为i的情况
memset(dp,-,sizeof(dp));
mod=i;
ans+=dfs(pos,,,); //搜索数位和为i的合法数的个数
}
return ans;
}
int main(){
int t;
scanf("%d",&t);
int kase=;
while(t--){
scanf("%lld",&n);
printf("Case %d: %lld\n",++kase,solve(n));
}
return ;
}