本文主要是介绍UVa 11361 Investigating Div-Sum Property，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题居然提交了十次才过....期间小问题不断。思路的话基本是《训练指南》里面来的，不过有几个小问题需要注意一下。第一，当K在大于100的情况下，就直接输出0就可以了。因为a,b不超过2^31，可以估算出a,b最多十位十进制数，那么每位最大为9，所以各个数字之和是不可能超过100的，那么个数字之和为模K为0的条件是永远不可能到达的。
还有一点是，当剩余数字d=0时，当且仅当m1和m2都为0时，即f[0][0][0]为1，其余f[0][][]都为0。然后将已知的f[d][m1][m2]保存下来，递归求解即可。最后，书上提到在计算(m2-b)%k时若b很大m2-b小于0时怎么办。我的解决方法是，凡是遇到减法，则用式子(m2-b%k+k)%k计算（没有翻过书，可能有更简单的方法）。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#define MAX 32+5
#define MAXK 100+5
using namespace std;int f[MAX][MAXK][MAXK];
bool vis[MAX][MAXK][MAXK];
int T,k,A,B;
char temp[64];
int p[MAX];int recur(int,int,int);int main()
{//freopen("data.txt","r",stdin);cin>>T;f[0][0][0]=1;//d为0时，只有m1,m2都为0，才为1p[0]=1;for(int i=1;i<32;++i) p[i]=10*p[i-1];while(T--){cin>>A>>B>>k;if(k>100){//k>100结果必为0cout<<0<<endl;continue;}A--;sprintf(temp,"%d",A);//整数转化为字符串string a(temp);sprintf(temp,"%d",B);string b(temp);memset(vis,0,sizeof(vis));int ans,pos=ans=0;int m1,m2=m1=0;while(pos<b.size()){for(int i=0;i<b[pos]-'0';++i){ans+=recur(b.size()-1-pos,(m1-i%k+k)%k,(m2-i*p[10,b.size()-pos-1]%k+k)%k);}m1=(m1-(b[pos]-'0')%k+k)%k;m2=(m2-(b[pos]-'0')*p[10,b.size()-pos-1]%k+k)%k;pos++;}ans+=f[0][m1][m2];m1=m2=pos=0;while(pos<a.size()){for(int i=0;i<a[pos]-'0';++i){ans-=recur(a.size()-1-pos,(m1-i%k+k)%k,(m2-i*p[10,a.size()-pos-1]%k+k)%k);}m1=(m1-(a[pos]-'0')%k+k)%k;m2=(m2-(a[pos]-'0')*p[10,a.size()-pos-1]%k+k)%k;pos++;}ans-=f[0][m1][m2];cout<<ans<<endl;}return 0;
}int recur(int d,int m1,int m2)
{if(vis[d][m1][m2]||d==0) return f[d][m1][m2];f[d][m1][m2]=0;for(int i=0;i<10;++i){f[d][m1][m2]+=recur(d-1,(m1+k-i%k)%k,(m2-i*p[10,d-1]%k+k)%k);}vis[d][m1][m2]=1;return f[d][m1][m2];
}这篇关于UVa 11361 Investigating Div-Sum Property的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
