Time Limit: 1 second Memory Limit: 128 MB
【问题描述】
Sramoc（K,M）表示用数字0，1，2，。。。，K-1组成的自然数中能被M整除的最小数。给定K,M，求Sramoc（K,M）。 例如，K=2,M=7时，Sramoc（K,M）＝1001。 【输入格式】
输入文件第一行为两个整数K,M，满足2<=k<=10，1<=m<=1000。
【输出格式】
输出文件包含Sramoc（K,M）的值。
Sample Input
2 7 Sample Output
1001 【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t085
【题意】 按照数据,不一定要用满k个数字,可以只用一部分.
【题解】 这个用同余率来搞吧; 每次增加一位的时候只要知道前n-1位的模m的值就好了; 然后*10+新加上的数字然后再对m取模;就是n位数的模m值了; 然后可以用一个二维数组bo[i][j]来判重,表示最后一位数字为i,余数为j的情况有没有出现过; 用广搜吧； 加上那个判重; 很容易写出程序; 程序在队列的基础上写了个递归的输出过程; 这样就不用把整个数字都记录下来了(这个数字多大都没关系了); 【完整代码】
#include <cstdio>#include <algorithm>#include <cmath>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%I64d",&x)typedef pair<int,int> pii;typedef pair<LL,LL> pll;const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int MAXN = 110;struct abc{ int PRe,num,last;};int k,m,l,r;abc dl[500000];bool bo[10][2000];void output_ans(int now){ if (now==0) return; output_ans(dl[now].pre); printf("%d",dl[now].last);}int main(){ //freopen("F://rush.txt","r",stdin); rei(k);rei(m); rep1(i,1,k-1) { if (i%m==0) { printf("%d/n",i); return 0; } if (bo[i][i%m]) continue; bo[i][i%m] = true; abc temp; temp.pre = 0; temp.num = i%m; temp.last = i; dl[++r] = temp; } l = 0; while (l < r) { abc tou = dl[++l]; int now = tou.num; rep1(i,0,k-1) { int rest = (now*10+i)%m; if (!bo[i][rest]) { bo[i][rest] = true; abc temp1; temp1.num = rest; temp1.pre = l; temp1.last = i; dl[++r] = temp1; if (rest==0) { output_ans(r); return 0; } } } } return 0;}新闻热点
疑难解答
