数字游戏（二）
题目描述
由于科协里最近真的很流行数字游戏，某人又命名了一种取模数，这种数字必须满足各位数字之和mod N为0。现在大家又要玩游戏了，指定一个整数闭区间[a,b]，问这个区间内有多少个取模数。 输入 题目有多组测试数据。每组只含三个数字a,b,N。
输出
对于每个测试数据输出一行，表示各位数字和mod N为0的数的个数。
样例输入
1 19 9
样例输出
2
对于全部数据，1<=a,b<=2^31-1,1<=N<100。
解析：
STEP1：判断算法
根据数据范围，a,b<=1^31-1,也就是在int范围内，同时这使我们确定了用常规方法（暴力）没有办法AC，毕竟O（n）的算法都会TLE， 所以
可以肯定这是一道在数位上做文章的题，也就是数位dp
STEP2：找到状态
由于上一步已经知道这是一道数位dp，所以便可以很轻易的得知一定有一个维度属于数位，那我们思考一下，还有没有其他要记录的的呢？
很明显还有%n余几，所以dp[i][j]表示位数<=i的所有数中%n余j的数的个数。
STEP3：状态转移
一个数在末尾加一个k，这样dp（位数+1）（（k+原来%n）%n），可以稍微展示一下我的dp方程
for(int i=2;i<=q;i++)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<=9;k++)
{
dp[i][j]+=dp[i-1][(j-k+n*10)%n];
}
}
}
但是dp方程虽然求出来了，但还有一个很大的问题，就是它的左右端点不一定完美的是一个位数的左右端点，所以还得再处理一下
STEP4：solve处理
l到r之间的所有取模数可以看做1到r之间的所有取模数与1到l-1之间的所有取模数之差，所以solve（x）就只用计算1-x之间的取模数
最后，solve有三个参数，分别是x，y，w，x是这个数，y是%n的值，而w是x的位数
对于每个x，可以将它的最高位剥掉，然后将它加上对应的值，不断循环此过程，最后就出来答案了
注意事项
1.这题是多组数据！！！
2.记得初始化！！！
3.int再判断位数的时候会炸，要开long long！！！
4.l有可能是0，所以最后要加上1！！！
最后代码上来：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int xx1=1,xx2=1,p,q;
int dp[105][205];
int ans;
int l,r,n;
int zgw(int x)
{
int ans_=1;
for(int i=1;i<=x-1;i++)
{
ans_*=10;
}
return ans_;
}
int sovle(int x,int y,int w)
{
int ans2=0;
int s=9;
int ss=1;
while(x>s && w==-1)
{
s=s*10+9;
ss++;
}
if(w!=-1) ss=w;
if(ss==1)
{
y=y%n;
if(x<y) return 0;
return (x-y)/n+1;
}
for(int i=0;i<=x/zgw(ss)-1;i++)
{
ans2+=dp[ss-1][(11*n-i+y)%n];
}
return ans2+sovle(x%zgw(ss),(11*n-x/zgw(ss)+y)%n,ss-1);
}
signed main()
{
while(scanf("%lld%lld%lld",&l,&r,&n)!=EOF)
{
memset(dp,0,sizeof(dp));
xx1=1,xx2=1;
ans=0;
if(!l) l++;
for(int i=1;i<=15;i++)
{
if(xx1>l/10)
{
p=i;
break;
}
xx1*=10;
}
for(int i=1;i<=15;i++)
{
if(xx2>r/10)
{
q=i;
break;
}
xx2*=10;
}
q-=1;
for(int i=0;i<=9;i++) dp[1][i%n]++;
for(int i=2;i<=q;i++)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<=9;k++)
{
dp[i][j]+=dp[i-1][(j-k+n*10)%n];
}
}
}
if(l==0) printf("%lld\n",sovle(r,0,-1)-sovle(l-1,0,-1)+1);
else printf("%lld\n",sovle(r,0,-1)-sovle(l-1,0,-1));
}
return 0;
}
原文：https://www.cnblogs.com/chen-1/p/11351866.html