题意:问你从[1,N]有多少个数能被自身的SOD（sum of digits）整除
题解：数位dp，枚举SOD，因为最多只有12位，所以只要枚举1到12*9，一维记录pos，二维记录当前剩余要达到的SOD，三维记录当前的余数。因为取余对+-*没有影响，我们可以在前往下一个pos的同时对原来的余数*10再加上当前pos所枚举到的数，再进行取余就是到达下一个pos的余数。
#include<bits/stdc++.h> //CLOCKS_PER_SEC #define se second #define fi first #define ll long long #define Pii pair<int,int> #define Pli pair<ll,int> #define ull unsigned long long #define pb push_back #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) const double Pi=3.14159265; const int N=1e4+10; const ull base=163; const int INF=0x3f3f3f3f; const ll mod=1e9+7; using namespace std; ll dp[20][200][200];int a[20]; int o=0; ll dfs(int pos,int sta1,int sta2,bool lead,bool limit){ if(pos==-1){ return sta1==0&&sta2==0; } if(!limit&&!lead&&dp[pos][sta1][sta2]!=-1)return dp[pos][sta1][sta2]; int up=limit?a[pos]:9; ll ans=0; for(int i=0;i<=up&&sta1-i>=0;i++){ ans+=dfs(pos-1,sta1-i,(sta2*10+i)%o,lead&&i==0,limit&&i==a[pos]); } if(!limit&&!lead)dp[pos][sta1][sta2]=ans; return ans; } ll solve(ll x){ int pos=0; while(x){a[pos++]=x%10;x/=10;} int up=9*pos;ll ans=0; for(int i=1;i<=up;i++){ memset(dp,-1,sizeof(dp)); o=i; ans+=dfs(pos-1,i,0,1,1); } return ans; } int main(){ int T;scanf("%d",&T);int tt=1; while(T--){ ll x;scanf("%lld",&x); printf("Case %d: %lld ",tt++,solve(x)); } return 0; }