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;}新聞熱點
疑難解答
