Time Limit: 1 second Memory Limit: 128 MB
【問(wèn)題描述】
Sramoc（K,M）表示用數(shù)字0，1，2，。。。，K-1組成的自然數(shù)中能被M整除的最小數(shù)。給定K,M，求Sramoc（K,M）。 例如，K=2,M=7時(shí)，Sramoc（K,M）＝1001。 【輸入格式】
輸入文件第一行為兩個(gè)整數(shù)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
【題意】 按照數(shù)據(jù),不一定要用滿k個(gè)數(shù)字,可以只用一部分.
【題解】 這個(gè)用同余率來(lái)搞吧; 每次增加一位的時(shí)候只要知道前n-1位的模m的值就好了; 然后*10+新加上的數(shù)字然后再對(duì)m取模;就是n位數(shù)的模m值了; 然后可以用一個(gè)二維數(shù)組bo[i][j]來(lái)判重,表示最后一位數(shù)字為i,余數(shù)為j的情況有沒(méi)有出現(xiàn)過(guò); 用廣搜吧； 加上那個(gè)判重; 很容易寫出程序; 程序在隊(duì)列的基礎(chǔ)上寫了個(gè)遞歸的輸出過(guò)程; 這樣就不用把整個(gè)數(shù)字都記錄下來(lái)了(這個(gè)數(shù)字多大都沒(méi)關(guān)系了); 【完整代碼】
#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;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
