求解一个题。。
Sramoc问题
描述
Sramoc ( K , M ) 表示用数字0、1、2…、K-1组成的自然数中能被M整除的最小数。给定 K、M，求Sramoc ( K,M )。例如 K=2，M=7的时候，Sramoc( 2 , 7 ) = 1001。
输入
第一行为两个整数K、M满足2<=K<=10、1<=M<=1000。
输出
输出Sramoc(K,M)。
样例输入
2 7
样例输出
1001
#include <stdio.h>int Sramoc(int k,int m){ int l,rlt; int r[6]={0,0,0,0,0,0}; while(1){ for(l=0;l<6;l++){ if(++r[l]<k) break; r[l]=0; } rlt=r[0]+r[1]*1e1+r[2]*1e2+r[3]*1e3+r[4]*1e4+r[5]*1e5; if(rlt%m==0) return rlt; } return -1;}void main(){ int k,m; scanf("%d %d",&k,&m); printf("%d",Sramoc(k,m));}因为不确定位数，所以最好用广搜。另外，为了避免诸如超空间、超时之类的问题，有如下处理方法： 1：队列维护三个值，最后一位的数字，当前的余数，还有就是其前趋。 2：开一个哈希表：hash[i][j]表示尾数为i，余数为j是否出现过。 这样就能极大地减小枚举量。因为这样做的话，如果尾数一样余数也一样，就等于做了无用功，重复入队了。这样就能极大地减少无效状态。 一旦出现第一个余数为0的，就直接输出，结束。 Code:#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>using namespace std; int k,m;struct point{ int x,mod,f; }q[5000000];bool hash[10][1000]; void dfs(int x){ if (x==-1) return; dfs(q[x].f); printf("%d",q[x].x); } int main(){ freopen("sramoc.in","r",stdin); freopen("sramoc.out","w",stdout); scanf("%d%d",&k,&m); int l=0,r=0; for (int i=1; i<k; i++) { q[r].x=i; q[r].f=-1; q[r++].mod=(i % m); hash[i][(i % m)]=1; if (!(i % m)) { printf("%d\n",i); fclose(stdin); fclose(stdout); exit(0); } } while (l<r) { point tmp=q[l++]; for (int i=0; i<k; i++) { point now=tmp; now.x=i; now.f=l-1; now.mod=(tmp.mod*10+i)%m; if (!hash[now.x][now.mod]) { q[r++]=now; hash[now.x][now.mod]=1; } if (!now.mod) { dfs(r-1); printf("\n"); fclose(stdin); fclose(stdout); exit(0); } } }return 0;}