发现只要Σa[i]*i%Σa[i]==0就可以。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; long long t,l,r,dp[20][1600][170],bit[20],ret=0; void get_bit(long long x) { ret=0; while (x) {bit[++ret]=x%10;x/=10;} } long long dfs(long long pos,long long val1,long long val2,bool flag) { if (!pos) { if (!val2) return 1; return val1%val2==0; } if ((!flag) && (~dp[pos][val1][val2])) return dp[pos][val1][val2]; long long ans=0,up=flag?bit[pos]:9; for (long long i=0;i<=up;i++) ans+=dfs(pos-1,val1+i*pos,val2+i,flag&&i==up); if (!flag) dp[pos][val1][val2]=ans; return ans; } long long work(long long x) { if (x==-1) return 0; get_bit(x); return dfs(ret,0,0,1); } int main() { scanf("%lld",&t);memset(dp,-1,sizeof(dp)); for (long long i=1;i<=t;i++) { scanf("%lld%lld",&l,&r); printf("%lld ",work(r)-work(l-1)); } return 0; }