基本公式
（a+b)%mod=(a%mod+b%mod)%mod
设一个任意整数\(A=a*10^n+b*10^{n-1}+...+c\).
由此可以证明 \(A \quad mod \quad m=(((a \quad mod \quad m)*10+b \quad mod \quad m)*10...)+c) \quad mod \quad m\)
该证明可以应用在数位DP
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200;
int l,r,dp[20][N][N];
int len,a[20],mod;
int dfs(int pos,int sum,int st,int limit)
{
if(sum+9*len<mod) return 0;
if(pos>len&&sum==0) return 0;
if(pos>len) return st==0&&sum==mod?1:0;
if(!limit&&dp[pos][sum][st]!=-1) return dp[pos][sum][st];
int ans=0;
int res=limit?a[len-pos+1]:9;
for(int i=0;i<=res;i++)
ans+=dfs(pos+1,sum+i,(10ll*st+i)%mod,i==res&&limit);//传st的时候就应用了这个证明
return limit?ans:dp[pos][sum][st]=ans;
}
int solve(int x)
{
len=0;
while(x) a[++len]=x%10,x/=10;
int ans=0;
for(mod=1;mod<=9*len;mod++)
{
memset(dp,-1,sizeof dp);
ans+=dfs(1,0,0,1);
}
return ans;
}
signed main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%lld%lld",&l,&r);
printf("%lld\n",solve(r)-solve(l-1));
return 0;
}