我的代码是错的，第一次是超时，后来看了人家的代码，才知道原来可以用一个数组来节省时间
我的错误的代码
原因：
搜索比n小的数字，此时为了搜索到的解 m 是最小的，应该从区间[0,s]的第s位开始向第0位搜索，因为在相同 pnum 情况下，把高位数字变小所得到的 m 值更小。
我的错误代码
#include "iostream" #include "math.h" #include "algorithm" #include "string.h" #define N 10000000; using namespace std; int top,list[120],MIN,m,n,flag,data[120][10]; int count(){ int i,num=0; //for(i=1;i<top;i++)cout<<list[i];cout<<endl;system("pause"); for(i=1;i<top;i++){ num+=data[i][list[i]]; } return num; } int min(int a,int b){return a>b?b:a;} void dfs(int s,int num){ int i,j; if(num==0){ int ans=count(); if(ans%m!=0)return; if(ans%m==0){flag=1;return;} //cout<<"*****"<<ans<<endl;system("pause"); } for(i=s;i<=top-num;i++){ if(i==top-1)j=1; else j=0; for(;j<=9;j++){ int tem=list[i]; list[i]=j; dfs(i+1,num-1); if(flag==1) return; list[i]=tem; } } } void make(){ int i,j; data[0][1]=1; for(i=1;i<120;i++){ data[i][1]=data[i-1][1]*10%m; for(j=2;j<10;j++){ data[i][j]=data[i][1]*j%m; } } } int main(){ int i; char s[120]; while(cin>>s>>m){ make(); top=1; for(i=strlen(s)-1;i>=0;i--){ list[top++]=(int)(s[i]-'0'); } //for(i=1;i<top;i++)cout<<list[i];cout<<endl;system("pause"); MIN=N;flag=0; for(i=1;i<top;i++){ dfs(1,i); if(flag==1)break; } for(i=top-1;i>=1;i--)cout<<list[i];cout<<endl; } }
大神的代码，附有一些解释
#include <stdio.h> #include <string.h> #include <iostream> #include <math.h> const int N = 110; #define _clr(a,val) (memset(a,val,sizeof(a))) typedef long long ll; using namespace std; int mod[N][10]; int num[N],path[N]; int rest[N][10010]; // rest[i][j] = k 表示搜索的区间是[0,i]，当前串对 m 的取余为 j 时，剩余的允许改变的数字次数为 k char str[N]; int kmod,len; void init() { int i,j; for(i = 0; i < 10; i++) mod[0][i] = i % kmod; for(i = 1; i < len; i++) { for(j = 0; j < 10; j++) mod[i][j] = ((10 % kmod) * (mod[i - 1][j] % kmod)) % kmod; } } int dfs(int pnum,int s,int pmod) // pnum：在区间 [0,s]内剩余允许改变的数字个数 s：当前搜索的区间[0，s] pmod：当前数字串对 k 求模的值 { //cout<<"pnum = "<<pnum<<" "<<s<<" "<<pmod<<endl; if(!pmod) { for(int i = len - 1; i >= 0; i--) printf("%d",path[i]); printf(" "); return 1; } int tmod; if(pnum == 0 || rest[pnum][pmod] > s) return 0; // 剪枝 当前剩余的改变次数为零，或者在搜索的区间内，且当前对数字串m对 kmod 取余为 pmod时，剩余的修改(使得pmod == 0）数字次数 大于 区间时。直接返回 for(int i = s; i >= 0; i--) // 搜索比n小的数字，此时为了搜索到的解 m 是最小的，应该从区间[0,s]的第s位开始向第0位搜索，因为在相同 pnum 情况下，把高位数字变小所得到的 m 值更小。 { for(int j = 0; j < num[i]; j++) { if(i == len - 1 && j == 0) continue; tmod = (pmod - (mod[i][num[i]] - mod[i][j]) + kmod) % kmod; // 当把 m 的第i位数字 m[i] 改为j时，我们已经有((10^i)*m[i])%k的值存放在数组mod[i][m[i]]中，又有((10^i)*j)%k的值存放在数组mod[i][j]中，那么把m值改小前后的变化值为（mod[i][m[i]]- mod[i][j]） path[i] = j; if(dfs(pnum - 1,i - 1,tmod)) return 1; } path[i] = num[i]; } for(int i = 0; i <= s; i++) // 搜索比 n 大的，应该从区间的开始搜索，这样能保证最小 { for(int j = num[i] + 1; j < 10; j++) { if(i == len - 1 && j == 0) continue; tmod = (pmod + (mod[i][j] - mod[i][num[i]])) % kmod; path[i] = j; if(dfs(pnum - 1,i - 1,tmod)) return 1; } path[i] = num[i]; } rest[pnum][pmod] = s + 1; return false; } int main() { int i; //freopen("data.txt","r",stdin); while(scanf("%s",str) != EOF) { len = strlen(str); scanf("%d",&kmod); init(); _clr(rest,0); int tmod = 0; for(i = 0; i < len; i++) { num[i] = path[i] = (str[len - 1 - i] - '0'); tmod = (tmod + mod[i][num[i]]) % kmod; } i = 0; while(1) { if(dfs(i++,len - 1,tmod)) break; } } return 0; }