定问在[A,B] 中,有多少个整数本身能被m整除,各个数位上数字之和也能被m整除?
#include <iostream> #include <cstring> #include <vector> using namespace std; vector<int> a; int m,f[40][105][105][2]; int dfs(int x,int v1,int v2,int flg){ if(x<0) return (v1==0&&v2==0); if(f[x][v1][v2][flg]!=-1) return f[x][v1][v2][flg]; int end= (flg?a[x]:9); int t=0; for(int i=0;i<=end;i++){ t+=dfs(x-1,(v1+i)%m,(v2*10+i)%m,flg&&(i==end)); } if(flg==0) f[x][v1][v2][flg]=t; return t; } int sov(int x){ a.clear(); memset(f,-1,sizeof f); while(x){ a.push_back(x%10); x/=10 ; } return dfs(a.size()-1,0,0,1); } signed main(){ int tes; cin>>tes; while(tes--){ int x,y; cin>>x>>y>>m; if(m>=100){ cout<<0<<endl;continue;} cout<< sov(y)-sov(x-1) <<endl; } }
标签:tes,int,Sum,11361,Investigating,UVA,include From: https://www.cnblogs.com/towboa/p/17333872.html